연속 부분 합의 최댓값

N개의 정수로 이루어진 배열에서 연속된 부분 배열의 합 중 최댓값을 출력하라. 부분 배열의 길이는 1 이상이다.

입력

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 1,000)
둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. (-10,000 ≤ 각 값 ≤ 10,000)

출력

연속 부분 배열의 합 중 최댓값을 출력한다.

예제 입력 1

8
-2 1 -3 4 -1 2 1 -5

예제 출력 1

6

예제 입력 2

5
1 2 3 4 5

예제 출력 2

15