• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت
• منبع: آزمون عملی دوره ۲۰ المپیاد کامپیوتر

شهر مقدّس آنیتا در یونان باستان شهری بود که تمام ساختمان­‌های آن در یک ردیف ساخته شده بود. با وجود قدیمی بودن، این شهر از ساختمان­‌های بلند ساخته شده بود و همچنین عرض هر ساختمان در این شهر دقیقا ۱ متر بود. نقل است که در این شهر، به هنگام بارش باران آب تا جای ممکن بر روی ساختمان­‌ها جمع می­‌شود. در واقع اگر این شهر را روی یک خط از راست به چپ در نظر بگیریم، آب جمع شده روی ساختمان­ها فقط از راست و چپ می­‌ریخت.

در یونان قدیم، یک سال کامل باران آمد. می‌خواهیم ببینیم در این صورت روی سقف ساختمان‌­های آنیتا حداکثر چه مقدار آب جمع شده است.

ورودی

در سطر اوّل ورودی عدد طبیعی $n$ (تعداد ساختمان‌ها) آمده است.

در سطر بعد $n$ عدد آمده است که به ترتیب ارتفاع ساختمان‌ها را از راست به چپ مشخّص می‌کنند و با فاصله از هم جدا شده اند.

ارتفاع هر ساختمان حداکثر ۱۰۰۰ متر خواهد بود. $$1 \leq n \leq 1\ 000\ 000$$

خروجی

در تنها خط خروجی حداکثر میزان آب جمع شده روی سقف ساختمان‌های شهر آنیتا (بر حسب متر مربّع) بنویسید.

زیرمسئله‌ها

مثال

ورودی نمونه ۱

7
4 1 3 5 2 3 4

خروجی نمونه ۱

7