- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- روز ۱ دوره ۳۱
مبین و مبینا میخواهند با بازی فکری جدیدی که پدربزرگشان، مستربین برایشان خریده است بازی کنند. مبین دفترچه راهنمای بازی را میخواند و بازی را برای مبینا شرح میدهد:
«این بازی فقط از تعدادی آجر تشکیل شده است. در ابتدا آجرها را در \(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 \:\) به ترتیب میآیند.
\[2 \leq n \leq 750\] \[1 \leq a_i \leq 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\) |
| ۴ | ۳۹ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
5
1 2 3 3 1
خروجی نمونه ۱
2
ورودی نمونه ۲
5
1 3 2 1 3
خروجی نمونه ۲
3