Question
Reduce array
Rahul visited Newton Land recently and he found an array arr consisting of n integers, such that the sum of all the elements of the array equals zero. In one operation, he can choose two different indices i and j (1 ≤ i, j ≤ n), decrease arr[i] by one, and increase arr[j] by one.
If i < j, the above operation is free, otherwise it takes one special coin.
What is the minimum special coin he needs to spend to make all the elements equal to 0?
If i < j, the above operation is free, otherwise it takes one special coin.
What is the minimum special coin he needs to spend to make all the elements equal to 0?
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains an integer n — the number of elements.
The next line contains n space separated integers arr1,…, arrn.
Constraints:
1 ≤ t ≤ 5000
1 ≤ n ≤ 105
−109 ≤ arr[i] ≤ 109
It is guaranteed that the sum of n over all test cases does not exceed 105
Each test case consists of two lines of input.
The first line of each test case contains an integer n — the number of elements.
The next line contains n space separated integers arr1,…, arrn.
Constraints:
1 ≤ t ≤ 5000
1 ≤ n ≤ 105
−109 ≤ arr[i] ≤ 109
It is guaranteed that the sum of n over all test cases does not exceed 105
Output
For each test case, print on new line, the minimum number of special coins he need to spend in order to make all the elements of the array equal to 0.
Example
Sample Input
1
4
-3 5 -3 1
Sample Output
3
Explanation
There's only test case. For this:
A possible strategy:
Do (i = 2, j = 3) three times (free), a = [−3, 2, 0, 1].
Do (i = 2, j = 1) two times (pay two coins), a=[−1, 0, 0, 1].
Do (i = 4, j = 1) one time (pay one coin), a=[0, 0, 0, 0].
1
4
-3 5 -3 1
Sample Output
3
Explanation
There's only test case. For this:
A possible strategy:
Do (i = 2, j = 3) three times (free), a = [−3, 2, 0, 1].
Do (i = 2, j = 1) two times (pay two coins), a=[−1, 0, 0, 1].
Do (i = 4, j = 1) one time (pay one coin), a=[0, 0, 0, 0].