+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- نلی $n$ تُنگ بلوری دارد که هرکدام دارای میزان مشخصی **شفافیت** هستند. او می‌خواهد همه‌ی تنگ‌ها را در یک ردیف و پشت سر هم قرار دهد. شفافیت تنگ $i$م برابر با $a_i$ است. اما به دلایل نه‌چندان منطقی، قرار گرفتن تنگ‌ها در کنار یکدیگر باعث می‌شود بعضی از آن‌ها ترک بخورند! میزان ترک خوردن هر تنگ به تنگ‌هایی که قبل و بعد از آن قرار گرفته‌اند بستگی دارد. توجه کنید که ترک خوردن یک تنگ باعث تغییر شفافیت آن نمی‌شود. فرض کنید در یک ترتیب، تنگ $i$ در جایگاهی مشخص قرار گرفته است. برای محاسبه‌ی میزان ترک خوردن این تنگ، از میان تمام تنگ‌هایی که **قبل از آن** قرار گرفته‌اند، شفاف‌ترین تنگ را $j$ و به همین شکل، از میان تمام تنگ‌هایی که **بعد از آن** قرار گرفته‌اند نیز شفاف‌ترین تنگ را $k$ در نظر می‌گیریم. سپس میزان ترک خوردن تنگ $i$ به صورت زیر تعیین می‌شود: + در صورتی که $a_i < min(a_j, a_k) \ $، تنگ $i$م به مقدار $min(a_j, a_k) - a_i \ $ ترک می‌خورد. + اگر $a_i > min(a_j, a_k) \ $ و $a_i < max(a_j, a_k) \ $، تنگ $i$م به مقدار $max(a_j, a_k) - a_i \ $ ترک می‌خورد. + اگر $a_i > max(a_j, a_k) \ $، تنگ $i$ ترک نمی‌خورد و میزان ترک خوردگی آن برابر با صفر است. برای اولین تنگ، فقط تنگ‌های بعد از آن را در نظر می‌گیریم و برای آخرین تنگ نیز فقط تنگ‌های قبل از آن را. همچنین، اگر در یک سمت هیچ تنگی وجود نداشته باشد، بیشترین شفافیت آن سمت را برابر با $0$ در نظر می‌گیریم. می‌دانیم شکنندگی یک ترتیب مشخص از تنگ ها برابر با مجموع مقدار ترک خوردگی $n$ تنگ است. نلی تنگ های خود را به امیرحسین داده و از او می‌خواهد تا به او بگوید در نهایت کمترین مقدار ممکن شکنندگی در میان تمام جایگشت‌های این $n$ تنگ چقدر خواهد بود، امیرحسین که ذهنش کمی مشغول است از شما برای یافتن پاسخ کمک می‌‌خواهد. # ورودی در خط اول، عدد صحیح $n$، تعداد تُنگ‌های بلوری، داده می‌شود. $$1 \leq n \leq 3*10^5$$ در خط دوم، $n$ عدد صحیح داده می‌شود که $a_i$ میزان شفافیت تنگ $i$ است، تضمین می‌شود هیچ دو تنگی با شفافیت برابر وجود ندارند. $$1 \leq a_i \leq 10^9$$ # خروجی در تنها خط خروجی، کمترین مقدار ممکن برای شکنندگی یک ترتیب از تنگ ها را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 3 1 4 2 5 ``` ## خروجی نمونه ۱ ``` 6 ``` ## ورودی نمونه ۲ ``` 7 7 1 10 2 6 8 12 ``` ## خروجی نمونه ۲ ``` 20 ```