شهر زنبور‌ها بر روی یک شاخه از یک درخت تنومند ساخته شده است. این شهر از $n$ ستون کنار هم تشکیل شده که آن‌ها را به ترتیب با ۱ تا $n$ شماره‌گذاری کرده‌ایم. در هر ستون تعدادی کندو وجود دارد، به طوری که کندوی اول به شاخه متصل است و کندو‌های بعدی هر کدام به کندوی بالایی خود متصلند. در نتیجه هر ستون ارتفاعی دارد که تعداد کندوهایی که در آن ستون وجود دارد، را مشخص می‌کند و آن را با $h_i$ نمایش می‌دهیم.

ملکه‌ی زنبورها برای کاهش ضرر در حمله‌ی خرس‌ها به تازگی دست به کار شده و گروهی را به سردستگی«هاچ زنبور عسل» مسئول این کار کرده است. در حمله‌ی یک خرس به شهر زنبورها، خرس تا جایی که می‌تواند می‌پرد و در نتیجه تمام کندوهایی که دستش به آن‌ها می‌رسد را می‌کند؛ ضرر یک حمله برابر تعداد کندوهایی است که خرس کنده است. در نتیجه هاچ باید کاری کند که در حمله‌ی یک خرس کم‌ترین تعداد کندو در دسترس خرس باشد.

در هر حرکت هاچ و دسته‌ی زنبورها می‌توانند یک کندو از پایین‌ترین جا در یک ستون را بردارند و به پایین‌ترین کندو در یکی از دو ستون مجاور متصل کنند؛ دقت کنید که تنها می‌توان در ستون‌های ۱ تا $n$ کندویی اضافه کرد. در این صورت ارتفاع این ستون یکی کم شده و به ارتفاع ستونی که کندو در آن قرار داده شده، یک واحد اضافه می‌شود. به دلیل حجم زیاد کار و کم‌بود زمان هاچ می‌خواهد در کم‌ترین حرکت، با جابه‌جا کردن کندوها به شیوه‌ی گفته شده کاری کند که در حمله‌ی یک خرس کم‌ترین خسارت به شهر وارد شود.

شما باید به‌دست بیاورید کم‌ترین تعداد حرکت برای این‌که هاچ این کار را انجام دهد چقدر است.

برنامه‌ای بنویسید که :

• تعداد و ارتفاع ستون‌های شهر را از ورودی بخواند.
• کم‌ترین تعداد حرکت برای این که هاچ ضرر را به حداقل برساند بیابید.
• پاسخ را در خروجی بنویسید.

سطر نخست ورودی شامل یک عدد صحیح است: $n$ که تعداد ستون‌های شهر را مشخص می‌کند $(1\leq n \leq1000)$ . سطر بعدی محتوی $n$‌عدد صحیح می‌باشد؛ عدد $i$ام نشانگر ارتفاع ستون $i$ام، $h_i$ است$(1\leq h_i \leq 10^6)$.

در تنها سطر خروجی یک عدد که نشانگر کم‌ترین تعداد حرکات لازم می‌باشد بنویسید.

• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۶۴ مگابایت