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.</p>

• 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$?

입력 형식

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

The next line is followed by $n$ integers $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$.

예제 입력 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