- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۱۲۸ مگابایت
- منبع: آزمون عملی دوره ۲۰ المپیاد کامپیوتر
شهر مقدّس آنیتا در یونان باستان شهری بود که تمام ساختمانهای آن در یک ردیف ساخته شده بود. با وجود قدیمی بودن، این شهر از ساختمانهای بلند ساخته شده بود و همچنین عرض هر ساختمان در این شهر دقیقا ۱ متر بود. نقل است که در این شهر، به هنگام بارش باران آب تا جای ممکن بر روی ساختمانها جمع میشود. در واقع اگر این شهر را روی یک خط از راست به چپ در نظر بگیریم، آب جمع شده روی ساختمانها فقط از راست و چپ میریخت.
در یونان قدیم، یک سال کامل باران آمد. میخواهیم ببینیم در این صورت روی سقف ساختمانهای آنیتا حداکثر چه مقدار آب جمع شده است.
ورودی
در سطر اوّل ورودی عدد طبیعی \(n\) (تعداد ساختمانها) آمده است.
در سطر بعد \(n\) عدد آمده است که به ترتیب ارتفاع ساختمانها را از راست به چپ مشخّص میکنند و با فاصله از هم جدا شده اند.
ارتفاع هر ساختمان حداکثر ۱۰۰۰ متر خواهد بود. \[ 1 \leq n \leq 1\ 000\ 000 \]
خروجی
در تنها خط خروجی حداکثر میزان آب جمع شده روی سقف ساختمانهای شهر آنیتا (بر حسب متر مربّع) بنویسید.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۱۰۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
7
4 1 3 5 2 3 4
خروجی نمونه ۱
7