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

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

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

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

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

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

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

• سوال بعد
• سوال قبل