Description

Uim works as a secretary at a company. There are $n$ messages to inform the boss. Each message has a "goodness" value, which affects the boss’s mood. After a message is delivered, the boss’s mood becomes his previous mood plus this message’s goodness. Initially, the boss’s mood is $0$. Once the boss’s mood falls below $0$, he will fly into a rage and fire Uim.

To avoid being fired, Uim already knows the goodness values of these messages (which are arranged in chronological order) and wants to know how to prevent the boss from getting angry.

Uim can use a technique called "daoxu" ("倒叙"). For example, given $n$ messages, Uim can choose any integer $k$ ($1 \leq k \leq n$), first report events $k$ to $n$, and then report events $1$ to $k-1$. In particular, when $k=1$, the messages are reported in the original order.

He wants to know how many such values of $k$ can keep the boss from getting angry.

Input Format

The first line contains an integer $n$ ($1 \le n \le 10^6$), the number of messages.

The second line contains $n$ integers. In chronological order, the $i$-th message has goodness $A_i$ ($-10^3 \le A_i \le 10^3$).

Output Format

One line with a single integer, the number of feasible choices of $k$.

4
-3 5 1 2

2

Hint

Sample Explanation:

Feasible reporting orders (by indices) are $2\rightarrow3\rightarrow4\rightarrow1$ or $3\rightarrow4\rightarrow1\rightarrow2$ (corresponding to $k=2$ and $k=3$, respectively).

Feasible reporting orders (by goodness values) are $5\rightarrow1\rightarrow2\rightarrow(-3)$ or $1\rightarrow2\rightarrow(-3)\rightarrow5$.

Constraints:

For $25\%$ of the testdata, $n \le 10^3$. For $75\%$ of the testdata, $n \le 10^4$. For $100\%$ of the testdata, $1 \le n \le 10^6$.

Translated by ChatGPT 5