You are given an array $a$ consisting of $n$ integers $a_1, a_2,...., a_n$.
The array is called beautiful if all prefix sums of the array are non-negative. Formally, the array is beautiful if:
An index $i(1 \le i \le n)$ of the array is good, if we cut the suffix starting at index $i$ from the array and append the suffix at the beginning of the array, the array becomes beautiful. Formally, an index $i$ is good if:
Find the number of good indices of array $a$.
Each input consists of multiple test cases. The first line contains a single integer $t(1 \le t \le 2\times 10^5)$ the number of sets of input data. This is followed by their description.
The first line of each test case contains a single integer $n\space(1 \le n \le 2\times 10^5)$ the size of the array $a$.
The second line of each test case contains $n$ space seperated integers $a_1,a_2,…,a_n$ denoting the array $a$$(-10^4 \le a_i \le 10^4)$.
It is guranteed that sum of $n$ of all test cases does not exceed $2 \times 10^{5}$.
For each test case, output the number of good indices of the array in seperated lines.
Input | Output |
---|---|
2 5 5 4 -1 -2 3 3 -1 -2 -3 | 3 0 |
In the first test case there are 3 good indices {1, 2, 5}.
Index 1 is good. If we select index 1, the array becomes {5, 4, -1, -2, 3}. The prefix sums of the array are {5, 9, 8, 6, 9}. All the elements of prefix sums are non-negative.
Index 2 is good. If we select index 2, the array becomes {4, -1, -2, 3, 5}. The prefix sums of the array are {4, 3, 1, 4, 9}. All the elements of prefix sums are non-negative.
Index 3 is not good. If we select index 3, the array becomes {-1, -2, 3, 5, 4}. The prefix sums of the array are {-1, -3, 0, 5, 9}. There are two negative prefix sums.