До чого доводять книжки...

Автор задач кожного дня сидить в бібліотеці, що погано впливає на його моральний стан. Як можна бачити, всі задачі на цьому контесті про книжки, що ж буде далі...

У вас є $n$ книжок, $i$-та з яких має цікавість $a_i$. Ви хочете прочитати деякі з них і отримати найбільше задоволення, тобто, щоб цікавість прочитаних книжок була максимальна. Проте, цікавість прочитаних книжок не завжди дорівнює просто сумі їх цікавостей. З часом вам починає набридати читати, і кожна наступна книжка буде не такою цікавою, як вдавалася до того. Більш формально, якщо у вас є якась множина книжок, то цікавість їх прочитання буде дорівнювати $S_1$ + $S_2$ + $S_3$ + ...+ $S_{|S|}$ - $|S|$ + 1, де $|S|$ — розмір множини $S$.

Скажіть максимальну цікавість множини книжок серед всіх підвідрізків $[l;r]$ ($1\le l\le r\le n$) масиву $a$.

Вхідні дані

Перший рядок містить одне ціле число $n$ ($1\le n\le 10^6$) — кількість книжок.

Другий рядок містить $n$ цілих чисел $a_i$ ($-10^9\le a_i\le 10^9$) — цікавості книжок.

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Приклади

Оцінювання

Гарантується, що рішення, які правильно працюють при $n\le 2000$ отримуватимуть принаймні $10$ балів.

Гарантується, що рішення, які правильно працюють при $a_i\le a_{i+1}$ для всіх $i<n$ отримуватимуть принаймні $20$ балів.