Divide the Sequence

Alice has a sequence A, She wants to split A into as much as possible continuous subsequences, satisfying that for each subsequence, every its prefix sum is not small than 0.

The input consists of multiple test cases.
Each test case begin with an integer n in a single line.
The next line contains $n$ integers $A_{1},A_{2}\cdots A_{n}$.
$1 \leq n \leq 1e6$
$-10000 \leq A[i] \leq 10000$
You can assume that there is at least one solution.

For each test case, output an integer indicates the maximum number of sequence division.

6
1 2 3 4 5 6
4
1 2 -3 0
5
0 0 0 0 0

6
2
5

ZSTU

2016 Multi-University Training Contest 5