Profit

Yeonjong started a company. Today is the N-th day since founding, and the profit for each day has been recorded.

One day Yeonjong grew curious about which stretch of consecutive days earned the most money in total.

For example, suppose today is the 6th day since founding and the daily profits are:

• Day 1: -3
• Day 2: 4
• Day 3: 9
• Day 4: -2
• Day 5: -5
• Day 6: 8

Here the stretch that earned the most is days 2 through 6, for a total of 14.

Given the daily profits, find the maximum total profit over any stretch of consecutive days.

The input consists of several test cases. The first line of each test case contains N (1 ≤ N ≤ 250,000). Each of the next N lines contains that day's profit P (-10,000 ≤ P ≤ 10,000), given in order starting from the first day. The last line of the input contains 0.

For each test case, print the maximum total profit over any stretch of consecutive days. The stretch must not be empty.