You're given an array $a$ of $n$ integers, such that $a_1 + a_2 + \cdots + a_n = 0$.

In one operation, you can choose two different indices $i$ and $j$ ($1 \le i, j \le n$), decrement $a_i$ by one and increment $a_j$ by one. If $i < 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 $0$?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$)  — the number of elements.

The next line contains $n$ integers $a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$). It is given that $\sum_{i=1}^n a_i = 0$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

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


-----Example-----
Input
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
3
0
4
1
8
3000000000
0



-----Note-----

Possible strategy for the first test case:   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]$.

Difficulty: interview

Starter code:

Solutions:
t=int(input())
while t>0 :
    n=int(input())
    a=list(map(int,input().split()))
    an=0
    s=0
    for i in a :
        if s+i>=0 :
            s+=i 
        else :
            s+=i
            an-=s 
            s=0
    print(an)
    t-=1 


T = int(input())

#lets = 'abcdefghijklmnopqrstuvwxyz'
#key = {lets[i]:i for i in range(26)}

for t in range(T):
  n = int(input())
  #n,k = map(int,input().split())
  a = list(map(int,input().split()))
  #a = input().split()
  d = False
  cu = 0
  cu_m = 0
  for i in range(n):
    cu += a[i]
    cu_m = min(cu_m,cu)
  
  print(-cu_m)

tests = int(input())
for t in range(tests):
    n = int(input())
    ls = list(map(int, input().split()))
    curr = 0
    res = 0
    for item in ls:
        curr += item
        if curr < res:
            res = curr
    print(-res)

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        alst = list(map(int, input().split()))
        ans = 0
        total = 0
        for a in alst:
            total -= a
            ans = max(ans, total)
        print(ans)
    
main()

for _ in range (int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    r=0
    avl=0
    for i in a:
        if i>0:
            avl+=i
        else:
            i=abs(i)
            d=min(avl,i)
            avl-=d
            r+=i-d
    print(r)

import bisect
import copy
import fractions
import functools
import heapq
import math
import random
import sys


def __starting_point():

    T = int(input())

    for t in range(T):
        N = int(input())
        A = list(map(int, input().split()))

        total = 0
        min_ = 0
        for a in A:
            total += a
            min_ = min(min_, total)

        print(str(abs(min_)))

__starting_point()

t = int(input())
for _ in range(t):
    n = int(input())
    A = list(map(int,input().split()))
    res = 0
    temp = 0
    for a in A:
        temp+=a
        res = min(res,temp)
    print(-res)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    pre = [0]*(n+1)
    for i in range(n):
        pre[i+1] = pre[i]+a[i]
    print(abs(min(pre)))

t = int(input())
while t:
    t += -1
    n = int(input())
    l = list(map(int, input().split()))
    ans = 0
    sm = 0
    for i in l:
        sm += i
        ans = min(ans, sm)
    print(abs(ans))

"""
Author: Q.E.D
Time: 2020-09-06 09:39:09
"""
T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    quota = 0
    for x in a:
        k = abs(x)
        if x >= 0:
            quota += k
        else:
            r = max(0, k - quota)
            quota -= (k - r)
            ans += r
    print(ans)


#!/usr/bin/env pypy3
	
from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

def ans(A):
	A = A[::-1]

	ret = float("-inf")
	s = 0
	for a in A:
		s += a
		ret = max(ret, s)

	return ret


T = int(input())
for t in range(T):
	input()
	A = list(map(int, input().split()))
	print(ans(A))


t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    min = 0
    s = 0
    for i in range(n):
        s = s + a[i]
        if s < min:
            min = s
    print(abs(min))


from collections import defaultdict as dd
import sys
input=sys.stdin.readline
t=int(input())
while t:
    n=int(input())
    #n,m=map(int,input().split())
    l=list(map(int,input().split()))
    st=0
    for i in range(n):
        if(l[i]>0):
            st+=l[i]
        else:
            if(st):
                mi=min(st,-l[i])
                st-=mi
    print(st)
    t-=1

from sys import stdin
from math import ceil
inp = lambda : stdin.readline().strip()

t = int(inp())

for _ in range(t):
    n = int(inp())
    a = [int(x) for x in inp().split()]
    cumm = 0
    ans = 0
    for i in range(n):
        cumm += a[i]
        if cumm < 0:
            ans = min(ans,cumm)
    print(-1*ans)

t=int(input())
for t in range(t):
	n=int(input())
	a=[int(x) for x in input().split(' ')]
	b=[0]
	for i in range(n):
		b.append(b[-1]+a[i])
	# print(b)
	mn=b[0]
	for x in b:
		mn=min(mn,x)
	print(abs(mn))



for _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    cnt = 0
    av = 0
    for i in range(n):
        if a[i]<0:
            cr = min(-1*a[i],av)
            a[i]+=cr
            av-=cr
            cnt+=a[i]
            a[i]=0
        else:
            av+=a[i]
    print(-1*cnt)

# cook your dish here
# code
#    ___________________________________
#   |                                   |
#   |                                   |
#   |        _,     _   _     ,_        |
#   |    .-'` /     \'-'/     \ `'-.    |
#   |   /    |      |   |      |    \   |
#   |  ;      \_  _/     \_  _/      ;  |
#   | |         ``         ``         | |
#   | |                               | |
#   |  ;    .-.   .-.   .-.   .-.    ;  |
#   |   \  (   '.'   \ /   '.'   )  /   |
#   |    '-.;         V         ;.-'    |
#   |        `                 `        |
#   |                                   |
#   |___________________________________|
#   |                                   |
#   |  Author      :   Ramzz            |
#   |  Created On  :   21-07-2020       |
#   |___________________________________|
#
#    _ __ __ _ _ __ ___  ________
#   | '__/ _` | '_ ` _ \|_  /_  /
#   | | | (_| | | | | | |/ / / / 
#   |_|  \__,_|_| |_| |_/___/___|
#

import math
import collections
from sys import stdin,stdout,setrecursionlimit
from bisect import bisect_left as bsl
from bisect import bisect_right as bsr
import heapq as hq
setrecursionlimit(2**20)

t = 1
t = int(stdin.readline())

for _ in range(t):
    n = int(stdin.readline())
    #s = stdin.readline().strip('\n')
    a = list(map(int, stdin.readline().rstrip().split()))
    
    ans = 0
    s = 0
    for i in range(n):
        s += a[i]
        if(s<0 and abs(s)>ans):
            ans = abs(s)
            
    print(ans)
    
    


from math import ceil
from collections import deque


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = 0
	s = 0
	for i in range(n):
		if a[i]<s:
			ans += s-a[i]
			s = 0
		else:
			s -= a[i]
	print(ans)


#Codeforces.com round #668
#Problem B
import sys

#
#BEGIN TEMPLATE
#
def input():
    return sys.stdin.readline()[:-1]

def getInt():
    #Assumes next line consists of only one integer and returns an integer
    return int(input())

def getIntIter():
    return list(map(int, input().split()))

def getIntList():
    return list(getIntIter())

#
#END TEMPLATE
#

for _ in range(getInt()):
    n = getInt()
    nums = getIntList()
    minSum = 0
    currSum = 0
    for num in nums:
        currSum += num
        minSum = min(currSum, minSum)
    print(abs(minSum))


for T in range(int(input())) :
    n = int(input())
    l = list(map(int,input().split()))
    bal = 0 
    ans = 0
    for i in l :
        if i >= 0 :
            bal += i
        else :
            if abs(i) > bal :
                ans += abs(i)-bal
                bal = 0
            else :
                bal += i 
    print(ans)

import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return list(map(int, sys.stdin.readline().split()))

def SI():
	return sys.stdin.readline().strip()
t = II()
for q in range(t):
	n = II()
	a = LI()
	d = [0]*n
	s = 0
	for i in range(n):
		s+=a[i]
		d[i] = s
	ans = min(d)
	if ans>0:
		ans = 0
	print(-ans)


import math
from collections import deque
from sys import stdin, stdout
from string import ascii_letters
import sys
letters = ascii_letters
input = stdin.readline
#print = stdout.write

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    need = sum([i for i in arr if i >= 0])
    was = 0
    have = [0] * n
    for i in range(n):
        if i != 0:
            have[i] = have[i - 1]
        if arr[i] > 0:
            have[i] += arr[i]
    for i in range(n - 1, -1, -1):
        if arr[i] < 0:
            bf = min(abs(arr[i]), have[i] - was)
            was += bf
            need -= bf
        else:
            was = max(0, was - arr[i])
    print(need)



t = int(input())
for i in range(t):
    n = int(input())
    l = list(map(int,input().split()))
    h = 0
    ans = 0
    for j in range(n):
        h+=l[j]
        if h<0:
            ans = max(ans,abs(h))
    print(ans)

for __ in range(int(input())):
    n = int(input())
    ar = list(map(int, input().split()))
    ans = 0
    a = 0
    b = 0
    for elem in ar:
        if elem < 0:
            if b > -elem:
                b += elem
                a += elem
            else:
                ans += abs(elem) - b
                b = 0
                a += abs(elem) - b
        else:
            b += elem
    print(ans)

# Lack of emotion causes lack of progress and lack of motivation. Tony Robbins

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    s=0
    ans=0
    for x in a:
        s+=x
        ans=min(ans,s)
    print(-ans)


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    m=a[0]
    s=a[0]
    for i in range(1,n):
        s+=a[i]
        m=min(m,s)
    print(max(abs(m),0))

import math

t = int(input())

for q in range(t):
    n = int(input())
    P = [int(i) for i in input().split()]
    c = 0
    res = 0
    for i in P:
        if i > 0:
            c += i
        elif i < 0:
            if i < -1 * c:
                res += abs(i + c)
                c = 0
            else:
                c += i
    print(res)
        


for _ in range(int(input())):
    n = int(input())
    arr = list(map(int,input().split()))
    pos = 0
    i = 0
    while i < n:
        if arr[i] < 0:
            if pos >= abs(arr[i]):
                pos += arr[i]
                arr[i] = 0
            else:
                arr[i] += pos
                pos = 0
        else:
            pos += arr[i]
        i += 1
    print(pos)


gans = []
for _ in range(int(input())):
    n = int(input())
    u = list(map(int, input().split()))
    cur = 0
    ans = 0
    for i in range(n):
        if u[i] == 0:
            continue
        if u[i] > 0:
            cur += u[i]
        else:
            u[i] = -u[i]
            if cur > u[i]:
                cur -= u[i]
            else:
                ans += u[i] - cur
                cur = 0
        #print(cur, u[i])
    gans.append(ans)
print('\n'.join(map(str, gans)))


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]

for _ in range(val()):
    n = val()
    l = li()


    ans = curr = 0
    for i in l:

        if i >= 0:
            curr += i
            continue
        else:
            temp = min(curr, abs(i))
            curr -= temp
        if abs(i) > temp:
            ans += abs(i) - temp
    print(ans)


"""T=int(input())
for _ in range(0,T):
    n=int(input())
    a,b=map(int,input().split())
    s=input()
    s=[int(x) for x in input().split()]
    for i in range(0,len(s)):
        a,b=map(int,input().split())"""



T=int(input())
for _ in range(0,T):
    n=int(input())
    s=[int(x) for x in input().split()]
    nrem = 0
    ans=0
    for i in range(len(s)-1,-1,-1):
        if(s[i]>0):
            tt=min(nrem,s[i])
            s[i]-=tt
            ans+=s[i]
            nrem-=tt
        else:
            nrem+=abs(s[i])

    print(ans)