====== آقای بین (Mr.Bean) =====

مبین و مبینا می‌خواهند با بازی فکری جدیدی که پدربزرگشان، مستربین برایشان خریده است بازی کنند. مبین دفترچه راهنمای بازی را می‌خواند و بازی را برای مبینا شرح می‌دهد:

«این بازی فقط از تعدادی آجر تشکیل شده است. در ابتدا آجرها را در $n$ ردیف بچینید و  در ردیف $i$ام $a_i$ آجر را روی هم قرار دهید. شما در هر دقیقه می‌توانید تعدادی ردیف متوالی که تعداد آجرهای آن‌ها به یک اندازه است را انتخاب کنید و به همه‌ی آن‌ها به تعداد مساوی آجر اضافه کنید یا از آجر‌هایش بکاهید. به عبارتی دیگر می‌توانید یک بازه $l \leq r$ و عدد صحیح $x$ انتخاب کنید به طوری که $a_i = a_l$ به ازای تمامی $l \leq i \leq r$ برقرار باشد، سپس تمامی اعضای این بازه را با $x$ جمع کنید.

به طور مثال اگر دنباله 
$a = \langle 4, 2, 2, 2, 3, 2 \rangle$
باشد، می‌توانید با انتخاب بازه $l = 2$ و $r = 3$ و عدد صحیح $x = -1$ دنباله را به 
$a = \langle 4, 1, 1, 2, 3, 2 \rangle$
تبدیل کنید.

هدف بازی این است که در کمترین زمان ممکن کاری کنید که همه‌ی ردیف‌ها به یک اندازه آجر داشته باشند.»

مبین و مبینا که خیلی کوچک هستند از پس این بازی برنمی‌آیند و از شما کمک می‌خواهند تا کمترین زمان ممکن برای انجام بازی را پیدا کنید.

===== ورودی =====

در خط اول $n$ تعداد ردیف‌ها می‌آیند.

در خط دوم $n$ عدد $a_1, a_2, ..., a_n$ به ترتیب می‌آیند.

===== خروجی =====

کمترین زمان ممکن برای برابر کردن تعداد آجرهای تمامی ردیف‌ها را چاپ کنید.


===== زیرمسئله‌ها =====

  * زیرمسئله اول (۹ نمره): عدد طبیعی $x$ وجود دارد که $a_i \leq a_{i+1}$ به ازای تمامی $i < x$ و $a_i \geq a_{i+1}$ به ازای تمامی $i\geq x$ برقرار است.
  * زیرمسئله دوم (۲۰ نمره): $n \leq 100$
  * زیرمسئله سوم (۳۲ نمره): $n \leq 300$
  * زیرمسئله چهارم (۳۹ نمره): بدون محدودیت اضافی


===== محدودیت‌ها =====
  * محدودیت زمان: ۱ ثانیه
  * محدودیت حافظه: ۲۵۶ مگابایت

  * $2 \leq n \leq 750$
  * $1 \leq a_i \leq n$



===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|5 \\ 1 2 3 3 1|2|
|5 \\ 1 3 2 1 3|3|
</WRAP>

  * [[سوال ۲|سوال بعد]]