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

---

می‌خواهیم $n$ ساختمان $h_1, h_2, \dots, h_n$ طبقه‌ای کنار هم در یک ردیف بسازیم.

ساختمان در یک طبقه زمانی نورگیر است که از سمت چپ یا راست به فضای باز دسترسی داشته باشد. به‌‌عنوان مثال ساختمان‌های انتهای چیدمان (یعنی در سمت چپ یا راست)، تمام واحدهای آن نورگیر خواهند بود.

هدف این است که ساختمان‌ها را به ترتیبی بچینیم که تعداد واحدهای نورگیر به حداکثر برسد. تعداد حداکثری واحدهای نورگیر را پیدا کنید.

ورودی

در خط اول ورودی عدد $n$ تعداد ساختمان ها داده می شود. $$ 1 \leq n\leq 10^5 $$

سپس در خط بعدی به ترتیب $h_1$ تا $h_n$ داده می شود. $$ 1 \leq h_i\leq 10^9 $$

خروجی

در یک خط، حداکثر تعداد واحد های نورگیر را خروجی دهید.

مثال‌ها

ورودی نمونه ۱

3
1 3 2

خروجی نمونه ۱

5

ورودی نمونه ۲

5
1 3 3 3 3

خروجی نمونه ۲

10