CF1788E.Sum Over Zero

You are given an array $a_1, a_2, \ldots, a_n$ of $n$ integers. Consider $S$ as a set of segments satisfying the following conditions.

• Each element of $S$ should be in form $[x, y]$, where $x$ and $y$ are integers between $1$ and $n$, inclusive, and $x \leq y$.
• No two segments in $S$ intersect with each other. Two segments $[a, b]$ and $[c, d]$ intersect if and only if there exists an integer $x$ such that $a \leq x \leq b$ and $c \leq x \leq d$.
• For each $[x, y]$ in $S$, $a_x+a_{x+1}+ \ldots +a_y \geq 0$.

The length of the segment $[x, y]$ is defined as $y-x+1$. $f(S)$ is defined as the sum of the lengths of every element in $S$. In a formal way, $f(S) = \sum_{[x, y] \in S} (y - x + 1)$. Note that if $S$ is empty, $f(S)$ is $0$.

What is the maximum $f(S)$ among all possible $S$?

给你一个包含 $n$ 个整数的数组 $a_1, a_2, \ldots, a_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$；
• 对于 $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)$ 的最大值是多少？

The first line contains one integer $n$ ($1 \leq n \leq 2 \cdot 10^5$).

The next line is followed by $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$).

第一行包含一个整数 $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$）。

Print a single integer, the maximum $f(S)$ among every possible $S$.

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

In the first example, $S={[1, 2], [4, 5]}$ can be a possible $S$ because $a_1+a_2=0$ and $a_4+a_5=1$. $S={[1, 4]}$ can also be a possible solution.

Since there does not exist any $S$ that satisfies $f(S) \gt 4$, the answer is $4$.

In the second example, $S={[1, 9]}$ is the only set that satisfies $f(S)=9$. Since every possible $S$ satisfies $f(S) \leq 9$, the answer is $9$.

In the third example, $S$ can only be an empty set, so the answer is $0$.

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

由于不存在满足 $f(S) \gt 4$ 的 $S$，因此答案为 $4$。

在第二个例子中，唯一满足 $f(S)=9$ 的集合是 $S={[1, 9]}$。由于所有可能的 $S$ 均满足 $f(S) \leq 9$，因此答案为 $9$。

在第三个例子中，$S$ 只能是空集，因此答案为 $0$。