مبین و مبینا میخواهند با بازی فکری جدیدی که پدربزرگشان، مستربین برایشان خریده است بازی کنند. مبین دفترچه راهنمای بازی را میخواند و بازی را برای مبینا شرح میدهد:
«این بازی فقط از تعدادی آجر تشکیل شده است. در ابتدا آجرها را در n ردیف بچینید و در ردیف iام ai آجر را روی هم قرار دهید. شما در هر دقیقه میتوانید تعدادی ردیف متوالی که تعداد آجرهای آنها به یک اندازه است را انتخاب کنید و به همهی آنها به تعداد مساوی آجر اضافه کنید یا از آجرهایش بکاهید. به عبارتی دیگر میتوانید یک بازه l≤r و عدد صحیح x انتخاب کنید به طوری که ai=al به ازای تمامی l≤i≤r برقرار باشد، سپس تمامی اعضای این بازه را با x جمع کنید.
به طور مثال اگر دنباله a=⟨4,2,2,2,3,2⟩ باشد، میتوانید با انتخاب بازه l=2 و r=3 و عدد صحیح x=−1 دنباله را به a=⟨4,1,1,2,3,2⟩ تبدیل کنید.
هدف بازی این است که در کمترین زمان ممکن کاری کنید که همهی ردیفها به یک اندازه آجر داشته باشند.»
مبین و مبینا که خیلی کوچک هستند از پس این بازی برنمیآیند و از شما کمک میخواهند تا کمترین زمان ممکن برای انجام بازی را پیدا کنید.
در خط اول n تعداد ردیفها میآیند.
در خط دوم n عدد a1,a2,...,an به ترتیب میآیند.
کمترین زمان ممکن برای برابر کردن تعداد آجرهای تمامی ردیفها را چاپ کنید.
ورودی نمونه | خروجی نمونه |
---|---|
5 1 2 3 3 1 | 2 |
5 1 3 2 1 3 | 3 |