E. Сумма больше нуля
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$ из $$$n$$$ целых чисел. Рассмотрим набор отрезков $$$S$$$, удовлетворяющий следующим условиям.

  • Каждый элемент $$$S$$$ должен иметь вид $$$[x, y]$$$, где $$$x$$$ и $$$y$$$ — целые числа от $$$1$$$ до $$$n$$$ включительно, и $$$x \leq y$$$.
  • Никакие два отрезка в $$$S$$$ не пересекаются друг с другом. Два отрезка $$$[a, b]$$$ и $$$[c, d]$$$ пересекаются тогда и только тогда, когда существует такое целое число $$$x$$$, что $$$a \leq x \leq b$$$ и $$$c \leq x \leq d$$$.
  • Для каждого $$$[x, y]$$$ в $$$S$$$ выполняется $$$a_x+a_{x+1}+ \ldots +a_y \geq 0$$$.

Длина отрезка $$$[x, y]$$$ определяется как $$$y-x+1$$$. $$$f(S)$$$ определяется как сумма длин всех отрезков в $$$S$$$. Формально, $$$f(S) = \sum_{[x, y] \in S} (y - x + 1)$$$. Обратите внимание, что если $$$S$$$ пусто, то $$$f(S)$$$ равно $$$0$$$.

Каково максимальное значение $$$f(S)$$$ среди всех возможных $$$S$$$?

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

Во второй строке содержится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$).

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

Выведите одно целое число — максимальное $$$f(S)$$$ среди всех возможных $$$S$$$.

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

В первом примере $$$S=\{[1, 2], [4, 5]\}$$$ может являться $$$S$$$, так как $$$a_1+a_2=0$$$ и $$$a_4+a_5=1$$$. $$$S=\{[1, 4]\}$$$ также допустимо.

Поскольку не существует ни одного $$$S$$$, удовлетворяющего условию $$$f(S) > 4$$$, ответ — $$$4$$$.

Во втором примере $$$S=\{[1, 9]\}$$$ — единственное множество, которое удовлетворяет $$$f(S)=9$$$. Поскольку все возможные $$$S$$$ удовлетворяют $$$f(S) \leq 9$$$, ответ — $$$9$$$.

В третьем примере $$$S$$$ может быть только пустым множеством, поэтому ответ — $$$0$$$.