Max Sequence

Time Limit: 3000MS

Memory Limit: 65536K

Description

Give you N integers a1, a2 ... aN (|ai| <=1000, 1 <= i <= N).
You should output S.

Input

The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.

Output

For each test of the input, print a line containing S.

Sample Input

5
-5 9 -5 11 20
0

Sample Output

40

Hint

Source

N/A

提交代码