소들이 새로운 사업을 시작했고 Farmer John은 얼마나 잘하고 있는지 알고 싶다. 이 사업은 $N$($1 \leq N \leq 100{,}000$)일 동안 운영되었으며, 소들은 매일 $i$의 순이익 $P_i$($-1{,}000 \leq P_i \leq 1{,}000$)를 기록했다.

Farmer John은 소들이 임의의 연속한 기간 동안 얻은 총이익의 최댓값을 구하고 싶다. (연속한 기간의 길이는 하루부터 $N$일까지 가능하다.) 연속한 이익의 최대 합을 계산하는 프로그램을 작성하여 그를 도와주자.

입력

표준 입력에서 입력을 읽는다.

• 1번째 줄: 정수 $N$ 하나.
• $2..N+1$번째 줄: $i+1$번째 줄에는 정수 $P_i$ 하나가 주어진다.

출력

표준 출력으로 출력한다.

• 1번째 줄: 임의의 연속한 기간 동안 이익 합의 최댓값을 나타내는 정수 하나.

예제

입력 1

7
-3
4
9
-2
-5
8
-3

출력 1

14

참고

두 번째 수부터 여섯 번째 수까지(4, 9, -2, -5, 8)의 합을 구하면 최대 합인 14를 얻는다.

문제 작성자: Neal Wu, 2007