شهر زنبورها بر روی یک شاخه از یک درخت تنومند ساخته شده است. این شهر از $n$ ستون کنار هم تشکیل شده که آن‌ها را به ترتیب از ۱ تا $n$ شماره‌گذاری کرده‌ایم. در هر ستون تعدادی کندو وجود دارد، به طوری که کندوی اول به شاخه متصل است و کندوهای بعدی هر کدام به کندوی بالایی خود متصلند. در نتیجه هر ستون ارتفاعی دارد که آن را با $h_i$ نمایش می‌دهیم. (تعداد کندوهایی که در آن ستون وجود دارد) ملکهٔ زنبورها برای کاهش ضرر در حمله‌ٔ خرس‌ها به تازگی دست به کار شده و گروهی را به سردستگی «هاچ زنبور عسل» مسئول این کار کرده است. در حملهٔ یک خرس به شهر زنبور‌ها، خرس تا جایی که می‌تواند می‌پرد و در نتیجه تمام کندوهایی که دستش به آنها می‌رسد را می‌کند؛ ضرر یک حمله برابر تعداد کندوهایی است که خرس کنده است. در نتیجه هاچ باید کاری کند که در حملهٔ یک خرس کمترین تعداد کندو در دسترس خرس باشد. در هر حرکت هاچ و دستهٔ زنبورها می‌توانند یک کندو از پایین‌ترین جا در یک ستون را بردارند و به پایین‌ترین کندو در یکی از دو ستون مجاور متصل کنند؛ دقت کنید که تنها می‌توان در ستون‌های ۱ تا $n$ کندویی اضافه کرد. دراین صورت ارتفاع این ستون یکی کم شده و به ارتفاع ستونی که کندو در آن قرار داده شده، یک واحد اضافه می‌شود. به دلیل حجم زیاد کار و کمبود زمان هاچ می‌خواهد در کمترین تعداد حرکت، با جابجا کردن کندوها به شیوهٔ گفته شده کاری کند که در حملهٔ یک خرس کمترین خسارت ممکن به شهر وارد شود. شما باید به دست آورید کمترین تعداد حرکت برای اینکه هاچ این کار را انجام دهد چقدر است. برنامه‌ای بنویسید که تعداد و ارتفاع ستون‌های شهر را از ورودی بخواند و کمترین تعداد حرکت برای اینکه هاچ ضرر را به حداقل برساند را در خروجی بنویسد. ## محدودیت‌ها $$ 1 \leq n \leq 1000 $$ $$ 1 \leq h_i \leq 10^6 $$ + زبان C و C++ + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۵۰ مگابایت + زبان پایتون و جاوا + محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۰۰ مگابایت ## ورودی سطر نخست ورودی شامل یک عدد صحیح است: $n$ که تعداد ستون‌های یک شهر را مشخص می‌کند. سطر بعدی محتوی $n$ عدد صحیح می‌باشد؛ عدد $i$اُم نشان‌دهندهٔ ارتفاع ستون $i$اُم ($h_i$) است. ## خروجی در تنها سطر خروجی یک عدد که نشانگر کمترین تعداد حرکات لازم می‌باشد بنویسید. ## مثال ## نمونه ورودی ``` 5 4 1 1 2 2 ``` ## نمونه خروجی ``` 3 ```