N개의 정수로 이루어진 수열 A가 주어진다.

이 수열의 비어있지 않은 연속된 일부분을 선택하여 그 합이 최대가 되도록 하는 프로그램을 작성하시오.

예를 들어, 수열이 [10, -7, 5, 20, -35, 25, 10] 일 때, 연속된 구간 [25, 10]을 선택하면 합이 35로 최대가 된다.

단, 구간은 반드시 하나 이상의 원소를 포함해야 한다.

입력

첫 번째 줄에 수열의 크기 N이 주어진다.

두 번째 줄에 N개의 정수 Ai가 공백으로 구분되어 주어진다.

출력

연속된 구간의 합 중 최댓값을 출력한다.

제약 조건

1 ≤ N ≤ 100000

-1000 ≤ Ai ≤ 1000

예제 입력 1

5
1 -2 3 4 -5

예제 출력 1

7

예제 입력 2

3
-5 -1 -10

예제 출력 2

-1

예제 입력 3

10
10 -3 5 10 -20 5 8 -10 20 1

예제 출력 3

26