Алиса и Боб играют в очередную игру с карточками. На этот раз правила следующие. Перед ними в ряд лежат \(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\).
Алиса хочет сделать счет как можно больше. Боб удаляет такую карточку, чтобы счет стал как можно меньше.
Какой отрезок должна выбрать Алиса, чтобы счет был максимально возможным? Выведите максимальный счет.
Выходные данные
Выведите одно целое число — итоговый счет игры.
Примечание
В первом примере Алиса выбирает отрезок \([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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 -2 10 -1 4
|
6
|
|
2
|
8
5 2 5 3 -30 -30 6 9
|
10
|
|
3
|
3
-10 6 -15
|
0
|