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

---

دور دایره \(n\) عدد چیده شده‌اند که مقدار \(i\) امین عدد برابر \(a_i\) است.

دو نفر روی این دایره بازی میکنند به این شکل که در مرحله اول نفر اول یک خانه را انتخاب میکند و در مرحله دوم نفر دوم یک خانه بجز خانه نفر اول را انتخاب میکند.

سپس در مراحل بعد با شروع از نفر اول، هرکس در نوبتش یک خانه که مجاور حداقل یکی از خانه‌های انتخاب شده‌اش است و تا به حال انتخاب نشده را انتخاب میکند.

بازی زمانی تمام میشود که تمام خانه ها انتخاب شده باشند.

نفر اول میخواهد جمع خانه‌هایی که در نهایت انتخاب کرده، بیشینه شود اما نفر دوم میخواهد این مقدار کمینه شود.

اگر هر دو به بهترین شکل بازی کنند، جمع خانه‌هایی که نفر اول انتخاب میکند چند است؟

ورودی

در خط اول ورودی یک عدد \(n\) داده شده است. در خط دوم دنباله \(a_1,a_2,...,a_n\) داده شده است. \[2 \leq n \leq 500\ 000\] \[1 \leq a_i \leq 2\ 000\]

خروجی

جمع خانه‌هایی که نفر اول انتخاب میکند را خروجی دهید.

زیر مسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۲۰	\[n \le 300\]
۲	۲۰	\[n \le 5\ 000\]
۳	۲۰	تضمین می‌شود که بهترین حرکت اول نفر اول این است که خانه یک را انتخاب کند.
۴	۴۰	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4
7 6 8 4

خروجی نمونه ۱

13

ورودی نمونه ۱

5
1 1 1 1 1

خروجی نمونه ۱

3