لیته پس از این که در همکاری با فیته به موفقیت نرسید، تصمیم گرفت که از این‌جا به بعد با نیوفیته همکاری کند. نیوفیته از این اتفاق بسیار خرسند است اما برای این که کسی شک نکند ابتدا از لیته خواسته تا یک مسئله‌ی سخت را برایش حل کند، متاسفانه لیته با تمام مهارتی که در حل مسائل الگوریتمی دارد، این بار نیازمند کمک‌های شایان شماست تا در همکاری‌اش با نیوفیته با شکست مواجه نشود.
در این مسئله دنباله‌ای از اعداد صحیح به طول $n$ به شما داده می‌شود و شما باید با حداقل تعداد عملیات ممکن همه‌ی اعداد دنباله را تبدیل به صفر کنید. اعداد این دنباله از چپ به راست $a_1$ تا $a_n$ نامیده می‌شوند.
هر عملیات به این صورت است که ابتدا یک بازه از دنباله مانند $[l, r)$ انتخاب می‌کنید و از همه‌ی اعضای این بازه ۱ واحد کم می‌کنید. ($1 \le l < r \le n + 1$)
در خط اول ورودی، عدد طبیعی $n$ آمده‌است که طول دنباله را نشان می‌دهد.
در خط بعدی، $n$ عدد حسابی آمده است که به ترتیب $a_1$ تا $a_n$ را نشان می‌دهند.
در تنها خط خروجی، حداقل تعداد عملیات برای این که همه‌ی اعداد دنباله به صفر تبدیل شوند را چاپ کنید و در صورتی که این کار با عملیات‌های گفته شده امکان پذیر نیست عدد $-1$ را چاپ کنید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 10 1 1 1 1 2 2 2 3 2 1 | 5 |
| 8 2 2 2 0 1 1 2 2 | -1 |