정수 n개로 이루어진 수열이 주어진다. 이 수열에서 연속한 구간 하나를 골라 그 구간의 합을 계산할 때, 얻을 수 있는 합의 최댓값을 구하는 프로그램을 작성하라. 구간에는 수가 한 개 이상 반드시 포함되어야 한다.

첫 번째 예제의 경우 12와 21이 이어진 구간을 고르면 합이 33으로 가장 크다. 모든 수가 음수라면 가장 큰 음수 하나만 고르는 것이 답이 된다는 점에 주의하라.

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에 수열의 원소 n개가 공백으로 구분되어 주어지며, 각 원소는 -1,000 이상 1,000 이하의 정수다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

33

예제 입력 2

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2

14

예제 입력 3

5
-1 -2 -3 -4 -5

예제 출력 3

-1