Your friends have just opened a new business, and you want to see how well they are doing. The business has been running for a number of days, and your friends have recorded their net profit on each day. You want to find the largest total profit that your friends have made during any consecutive time span of at least one day.

Input

There will be several test cases in the input. Each test case will begin with an integer N (1 ≤ N ≤ 250,000) on its own line, indicating the number of days. On each of the next N lines will be a single integer P (-100 ≤ P ≤ 100), indicating the profit for that day. The days are specified in order. The input will end with a line with a single 0.

Output

For each test case, output a single integer, representing the maximum profit over any non-empty span of time. Print each integer on its own line with no spaces. Do not print any blank lines between answers.

Example

Input: 
6
-3
4
9
-2
-5
8
2
-1000
-19
0 

Output: 
14
-19