لیته پس از این که در همکاری با فیته به موفقیت نرسید، تصمیم گرفت که از این‌جا به بعد با نیوفیته همکاری کند. نیوفیته از این اتفاق بسیار خرسند است اما برای این که کسی شک نکند ابتدا از لیته خواسته تا یک مسئله‌ی سخت را برایش حل کند، متاسفانه لیته با تمام مهارتی که در حل مسائل الگوریتمی دارد، این بار نیازمند کمک‌های شایان شماست تا در همکاری‌اش با نیوفیته با شکست مواجه نشود.

در این مسئله دنباله‌ای از اعداد صحیح به طول $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$ را چاپ کنید.

• زیرمسئله اول (۳۰ نمره): $1 \le n \le 600$
• زیرمسئله دوم (۷۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le n \le 10^5$
• $0 \le a_i \le 10^5$ ($1 \le i \le n$)

• سوال بعد