D. Очередная очередная задача
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в очередную игру с карточками. На этот раз правила следующие. Перед ними в ряд лежат $$$n$$$ карточек. У $$$i$$$-й карточки значение $$$a_i$$$.

Сначала Алиса выбирает непустой последовательный отрезок карточек $$$[l; r]$$$ ($$$l \le r$$$). Затем Боб удаляет одну карточку $$$j$$$ из этого отрезка $$$(l \le j \le r)$$$. Счет игры равен сумме значений оставшихся на отрезке карточек $$$(a_l + a_{l + 1} + \dots + a_{j - 1} + a_{j + 1} + \dots + a_{r - 1} + a_r)$$$. В частности, если Алиса выбрала отрезок с ровно одним элементом, то после того, как Боб удалит единственную карточку, счет будет равен $$$0$$$.

Алиса хочет сделать счет как можно больше. Боб удаляет такую карточку, чтобы счет стал как можно меньше.

Какой отрезок должна выбрать Алиса, чтобы счет был максимально возможным? Выведите максимальный счет.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество карточек.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-30 \le a_i \le 30$$$) — значения на карточках.

Выходные данные

Выведите одно целое число — итоговый счет игры.

Примеры
Входные данные
5
5 -2 10 -1 4
Выходные данные
6
Входные данные
8
5 2 5 3 -30 -30 6 9
Выходные данные
10
Входные данные
3
-10 6 -15
Выходные данные
0
Примечание

В первом примере Алиса выбирает отрезок $$$[1;5]$$$ — весь ряд карточек. Боб удаляет карточку $$$3$$$ со значением $$$10$$$ из этого отрезка. Поэтому итоговый счет равен $$$5 + (-2) + (-1) + 4 = 6$$$.

Во втором примере Алиса выбирает отрезок $$$[1;4]$$$, и так как Боб удаляет либо карточку $$$1$$$, либо $$$3$$$, со значением $$$5$$$, то ответ становится $$$5 + 2 + 3 = 10$$$.

В третьем примере Алиса может выбрать любой из отрезков длины $$$1$$$: $$$[1;1]$$$, $$$[2;2]$$$ или $$$[3;3]$$$. Боб удаляет единственную карточку, поэтому счет равен $$$0$$$. Если Алиса выберет любой другой отрезок, то ответ будет меньше $$$0$$$.