+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + روز ۱ دوره ۳۰ ---------- لیته پس از این که در همکاری با فیته به موفقیت نرسید، تصمیم گرفت که از این‌جا به بعد با نیوفیته همکاری کند. نیوفیته از این اتفاق بسیار خرسند است اما برای این که کسی شک نکند ابتدا از لیته خواسته تا یک مسئله‌ی سخت را برایش حل کند، متاسفانه لیته با تمام مهارتی که در حل مسائل الگوریتمی دارد، این بار نیازمند کمک‌های شایان شماست تا در همکاری‌اش با نیوفیته با شکست مواجه نشود. در این مسئله دنباله‌ای از اعداد صحیح به طول $n$ به شما داده می‌شود و شما باید با حداقل تعداد عملیات ممکن همه‌ی اعداد دنباله را تبدیل به صفر کنید. اعداد این دنباله از چپ به راست $a_1$ تا $a_n$ نامیده می‌شوند. هر عملیات به این صورت است که ابتدا یک بازه از دنباله مانند $[l, r)$ انتخاب می‌کنید و از همه‌ی اعضای این بازه ۱ واحد کم می‌کنید. ($1 \le l < r \le n + 1$) + طول هر بازه که انتخاب می‌کنید باید توانی از ۲ باشد. + هر بازه حداکثر ۱ بار می‌تواند انتخاب شود. + اگر دو بازه‌ی انتخاب شده مانند $[l_2, r_2)$ و $[l_1, r_1)$ وجود داشته باشند که اشتراکشان تهی نباشد، آنگاه $max(l_1 - l_2, l_2 - l_1)$ باید مضربی از $min(r_1 - l_1, r_2 - l_2)$ باشد. # ورودی در خط اول ورودی، عدد طبیعی $n$ آمده‌است که طول دنباله را نشان می‌دهد. در خط بعدی، $n$ عدد حسابی آمده است که به ترتیب $a_1$ تا $a_n$ را نشان می‌دهند. $$ 1 \le n \le 10^5 $$ $$ 0 \le a_i \le 10^5 (1 \le i \le n) $$ # خروجی در تنها خط خروجی، حداقل تعداد عملیات برای این که همه‌ی اعداد دنباله به صفر تبدیل شوند را چاپ کنید و در صورتی که این کار با عملیات‌های گفته شده امکان پذیر نیست عدد $-1$ را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۳۰ | $ 1 \le n \le 600 $ | | ۲ | ۷۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 10 1 1 1 1 2 2 2 3 2 1 ``` ## خروجی نمونه ۱ ``` 5 ``` ## ورودی نمونه ۲ ``` 8 2 2 2 0 1 1 2 2 ``` ## خروجی نمونه ۲ ``` -1 ```

حل سؤال در بانک سؤالات