최대 연속 부분합

첫 줄에 수열의 길이 n (1 이상 12000 이하) 이 주어집니다. 둘째 줄에 n개의 정수가 주어집니다 (-10000 이상 10000 이하, 음수 가능).

연속한 부분 배열 중 합이 가장 큰 것의 합을 출력하세요. 부분 배열은 비어 있을 수 없습니다. 예를 들어 -2 1 -3 4 -1 2 1 -5 4 에서 4 -1 2 1 의 합 6 이 최대입니다.

예시

입력

9
-2 1 -3 4 -1 2 1 -5 4

출력

6