和の最大値

与えられた整数の並び a₁, a₂, a₃,... , a_n について、連続した項(1つ以上)の和の最大値を出力するプログラムを作成して下さい。

Input

複数のデータセットが与えられます。各データセットは以下のような形式です。

n
a1
a2
:
an

１行目に項数を表す整数 n (1 ≤ n ≤ 5000) が与えられます。続く n 行に第 i 項を表す整数 a_i (-100000 ≤ a_i ≤ 100000) が与えられます。

n が 0 のとき入力の最後とします（この場合は処理をしない）。

Output

各データセットに対して、連続した項の和の最大値を１行に出力して下さい。

Sample 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 for the Sample Input

19
14
1001

---