题目描述
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
输入格式
见题面
输出格式
见题面
样例输入
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