Вам дан массив \(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\)?
Выходные данные
Выведите одно целое число — максимальное \(f(S)\) среди всех возможных \(S\).
Примечание
В первом примере \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 -3 -2 5 -4
|
4
|
|
2
|
10
5 -2 -4 -6 2 3 -6 5 3 -2
|
9
|
|
3
|
4
-1 -2 -3 -4
|
0
|