游客 Signup | Login
中文 | En

1914 - 最大连续和

通过次数

0

提交次数

0

Time Limit : 5 秒 Memory Limit : 128 MB

给定一列数字A1,A2,A3...,An。求序列中一段连续的数字,使得它们的和最大。保证数字个数N≤1000,|Ai|≤10000

Input

对于每组数据,第一行是正整数N,描述数字的个数。第二行有N个数字,按一定的顺序给出。输入以N=0结束。

Output

对于每组数据,输出最大连续和。

Examples

Input Format

3
-1 1 0
5
1 2 3 4 -5
0

Output Format

1
10