给定一个由 $$$n$$$ 整数组成的数组 $$$a_1, a_2, \ldots, a_n$$$。将 $$$S$$$ 视为满足以下条件的一组段。
- $$$S$$$ 的每个元素应采用 $$$[x, y]$$$ 形式,其中 $$$x$$$ 和 $$$y$$$ 是 $$$1$$$ 和 $$$n$$$ 之间的整数(含),并且 $$$x \leq y$$$。
- $$$S$$$ 中没有两个线段彼此相交。当且仅当存在一个整数 $$$x$$$ 且满足 $$$a \leq x \leq b$$$ 和 $$$c \leq x \leq d$$$ 时,两个线段 $$$[a, b]$$$ 和 $$$[c, d]$$$ 相交。
- 对于 $$$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$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)。
下一行后面是 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$)。
输出
打印一个整数,即每个可能的 $$$S$$$ 中的最大值 $$$f(S)$$$。
示例
输入 #1
5 3 -3 -2 5 -4
输出 #1
4
输入 #2
10 5 -2 -4 -6 2 3 -6 5 3 -2
输出 #2
9
输入 #3
4 -1 -2 -3 -4
输出 #3
0
注意
在第一个示例中,$$$S=\{[1, 2], [4, 5]\}$$$ 可以是可能的 $$$S$$$,因为 $$$a_1+a_2=0$$$ 和 $$$a_4+a_5=1$$$。 $$$S=\{[1, 4]\}$$$ 也是一个可能的解决方案。
由于不存在任何满足$$$f(S) > 4$$$的$$$S$$$,所以答案是$$$4$$$。
在第二个示例中,$$$S=\{[1, 9]\}$$$ 是唯一满足 $$$f(S)=9$$$ 的集合。由于每个可能的 $$$S$$$ 都满足 $$$f(S) \leq 9$$$,所以答案是 $$$9$$$。
在第三个例子中,$$$S$$$只能是空集,所以答案是$$$0$$$。