B. Array Cancellation

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You're given an array aa of nn integers, such that a1+a2+⋯+an=0a1+a2+⋯+an=0.

In one operation, you can choose two different indices ii and jj (1≤i,j≤n1≤i,j≤n), decrement aiai by one and increment ajaj by one. If i<ji<j this operation is free, otherwise it costs one coin.

How many coins do you have to spend in order to make all elements equal to 00?

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤50001≤t≤5000). Description of the test cases follows.

The first line of each test case contains an integer nn (1≤n≤1051≤n≤105)  — the number of elements.

The next line contains nn integers a1,…,ana1,…,an (−109≤ai≤109−109≤ai≤109). It is given that ∑ni=1ai=0∑i=1nai=0.

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

Output

For each test case, print the minimum number of coins we have to spend in order to make all elements equal to 00.

Example

input

Copy

7 4 -3 5 -3 1 2 1 -1 4 -3 2 -3 4 4 -1 1 1 -1 7 -5 7 -6 -4 17 -13 4 6 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1 0

output

Copy

3 0 4 1 8 3000000000 0

Note

Possible strategy for the first test case:

Do (i=2,j=3)(i=2,j=3) three times (free), a=[−3,2,0,1]a=[−3,2,0,1].Do (i=2,j=1)(i=2,j=1) two times (pay two coins), a=[−1,0,0,1]a=[−1,0,0,1].Do (i=4,j=1)(i=4,j=1) one time (pay one coin), a=[0,0,0,0]a=[0,0,0,0].

解题说明：此题是一道模拟题，首先是要把所有免费的次数用完，从头开始遍历遇到正的数就累加，如果碰到负数，就能给尽可能给，最后剩下来的就是答案。

#include<stdio.h> int main() { int n, i, x, t; long long int sum; scanf("%d", &t); while (t--) { scanf("%d", &n); sum = 0; for (i = 0; i<n; i++) { scanf("%d", &x); sum += x; if (sum < 0) { sum = 0; } } printf("%lld\n", sum); } return 0; }