수익

연종이가 창업을 했다. 오늘은 창업한 지 N일째이고, 매일의 수익을 기록해 두었다.

어느 날 연종이는 어느 구간에서 돈을 가장 많이 벌었는지 궁금해졌다.

예를 들어 오늘이 창업한 지 6일째이고, 매일의 수익이 다음과 같다고 하자.

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

이때 가장 많은 돈을 번 구간은 2일부터 6일까지이며, 그 총 수익은 14이다.

매일의 수익이 주어질 때, 연속된 하루 이상의 구간에서 얻을 수 있는 최대 총 수익을 구하여라.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N이 주어진다 (1 ≤ N ≤ 250,000). 둘째 줄부터 N개의 줄에는 매일의 수익 P가 첫날부터 순서대로 주어진다 (-10,000 ≤ P ≤ 10,000). 입력의 마지막 줄에는 0이 주어진다.

각 테스트 케이스에 대해, 연속된 구간에서 얻을 수 있는 최대 총 수익을 출력한다. 단, 구간은 비어 있으면 안 된다.