题目描述

给定一个整数数组 $a_1, a_2, \ldots, a_n$，考虑 $S$ 作为满足以下条件的一组区间。

$1$、$S$ 的每个元素应该是 $[x, y]$ 的形式，其中 $x$ 和 $y$ 是介于 $1$ 和 $n$ 之间（包括边界值），并且 $x \leq y$ 。 $2$、$S$ 中的任意两个区间不相交。两个区间 $[a, b]$ 和 $[c, d]$ 相交当且仅当存在整数 $x$ 使得 $a \leq x \leq b$ 和 $c \leq x \leq d$。 $3$、对于 $S$ 中的每个 $[x, y]$，$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$。

在所有可能的 $S$ 中，最大的 $f(S)$ 是多少？。

输入格式

第一行包含一个整数 $n$；

接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

输出格式

输出一个整数，表示所有可能的 $S$ 中最大的 $f(S)$。

5
3 -3 -2 5 -4

4

样例分析

在第一个样例中，$S=\{[1,2],[4,5]\}$ 可能是一个可能的 $S$，因为 $a_1+a_2=0$ 且 $a_4+a_5=1$。$S=\{[1, 4]\}$ 也可能是一个可能的解。

由于不存在满足 $f(S) > 4$ 的 $S$，答案是 $4$。

数据范围与提示

对于 $100\%$ 的数据：$1 \leq n \leq 2 \cdot 10^5$，$-10^9 \leq a_i \leq 10^9$。