p00022 Maximum Sum Sequence
Given a sequence of numbers a1, a2, a3, ..., an, find the maximum sum of a contiguous subsequence of those numbers. Note that, a subsequence of one element is also a contiquous subsequence.



Input

The input consists of multiple datasets. Each data set consists of:


n
a1
a2
.
.
an


You can assume that 1 ≤ n ≤ 5000 and -100000 ≤ ai ≤ 100000.

The input end with a line consisting of a single 0.

Output

For each dataset, print the maximum sum in a line.

Example

Input

7
-5
-1
6
4
9
-6
-7
13
1
2
3
2
-2
-1
1
2
3
2
1
-2
1
3
1000
-200
201
0


Output

19
14
1001
```python
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(readline())
    if N == 0:
        return False
    mi = su = 0
    ans = -10**9
    for i in range(N):
        a = int(readline())
        su += a
        ans = max(ans, su - mi)
        mi = min(su, mi)
    print(ans)
    return True
while solve():
    ...


```