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

inputFormat

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.

outputFormat

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

样例

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

19
14
1001

</p>