길이가 N 인 수열 A_1, A_2, ..., A_N 이 주어질 때, 이 수열의 최대 구간 합을 구해보자.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 100) 이 주어진다.

둘째 줄에 정수 A_1, A_2, ..., A_N (-100 ≤ A_i ≤ 100) 이 주어진다.

출력

주어진 수열의 최대 구간 합을 출력한다.

예제 입력 1

4
-1 3 -2 4

예제 출력 1

5

예제 입력 2

3
-1 -2 -3

예제 출력 2

-1

참고

구간 합이란 수열의 연속한 부분을 합한 값이다. 예를 들어 [1, 2, 3] 의 구간 합은 [1] = 1, [1, 2] = 3, [1, 2, 3] = 6, [2] = 2, [2, 3] = 5, [3] = 3 으로 총 6개가 있다. 최대 구간 합이란 이 6개중 가장 큰 합을 말한다.

수열의 원소가 모두 음수가 아니라면 당연히 최대 구간 합은 모든 원소의 합과 같다. 하지만 수열에 음수가 포함된다면 그렇지 않을 수도 있다. 예를 들어, [-1, 3, -2, 4] 의 최대 구간 합은 [3, -2, 4] = 5 이다.

그러므로 모든 구간에 대해서 구간 합을 구해서 그 중 가장 큰 구간 합을 찾아야 한다. 가능한 구간의 개수는 총 ~N^{2}~개 있다.

누적 합 배열(Prefix sum array)를 사용하면 구간 합을 빠르게 구할 수 있다. 어떤 구간의 시작과 끝이 L, R (1 ≤ L ≤ R ≤ N) 일 때 누적 합 배열 P_1, P_2, ..., P_N 을 이용하면 A_L + A_{L+1} + ... + A_R 을 P_R - P_{L-1} 을 통해서 구할 수 있다.

** P_{L-1} 에서 L - 1 이 배열의 인덱스를 벗어날 수도 있는 것에 유의한다.**