SABBIRGAME - Sabbir and Game

no tags 

Sabbir is a little boy. he loves  to play. One day his friend taskin suggested a new interesting game. there are n levels in the game. one should pass all the levels with a positive life-point. in some level one can increase his life-point by defeating the villain of the game or lose some life-point when one can't defeat the villain. Sabbir knows the points he is going to lose or increase in each level. determine the mnimum life-point sabbir should have initially ( at the starting of the game ) to pass all the levels with a positive life point.

Input

input consists of at most 100 test cases.

first line consists of a single integer T ( 1 <= T <= 100) number of test cases

each test case is consists of two lines. first line consists of an integer n ( 1 <= n <= 1000 )

second line consists of n space separated integer  a1 , a2 ..... an-1 , an ( -107 <= ai  <= 107 ) 

Output

for each test case print an integer in one line , the minimum life-point sabbir will need initially.

Example

Input:
3
3
5 -8 3
4
1 2 -3 5
3
1 0 3
Output:
4
1
0
explanation:
first case, if sabbir have 4 life-points at first. sabbir will have 9 points after playing 1st level, he will have 1 point after playing 2nd level, he will have 4 points after playing 3rd level... his points never  becomes less than 1 (remains positive) . if he start with a lower point ( less than 4) initially, he will die at the 2nd level and can't pass all the levels. so, 4 is the minimum ans.

hide comments
aditya_rev: 2017-06-21 18:40:09

pls check for submission id 19654968. could u tell me where is the bug? thx before

itissabbir: 2017-04-30 09:27:52

@sachinverma there is a mistake in your code. I can't tell that in comments. try to find out.

Sachin verma: 2017-04-27 20:11:10

@sabbir will you please check my submission. I cannot understand my mistake. Thank you.

Marcin: 2017-03-18 22:07:28

What should be the answer for the following test case:
1
1
0

Should it be 0 or 1?

Edit: got it, it's 1

Last edit: 2017-03-18 22:15:57
Somdip Sen: 2017-03-14 11:44:17

sd_singh: what is it you need ?

Karsten Ari Agathon: 2017-03-07 07:28:05

I think it will be better if stated that the minimum life-point initially must larger or equal to 0.

shikhars387: 2017-02-22 21:00:36

Last edit: 2017-02-23 19:25:01
vengatesh15: 2017-02-22 18:21:52

Last edit: 2017-02-22 18:29:47
kira28: 2017-02-22 14:43:46

Same as http://www.spoj.com/problems/RPLC
But why my Binary-search solution(O(nlogn)) was faster than
ad-hoc (O(n)) :/

Last edit: 2017-02-23 13:49:46
vivek_singhvi: 2017-02-22 03:58:48

Easy 2 points :)


Added by:sabbir
Date:2017-02-21
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All