연속합 2

$n$개의 정수로 이루어진 수열이 주어진다. 이 수열에서 연속한 구간을 하나 골라 그 안의 수를 모두 더했을 때 얻을 수 있는 가장 큰 합을 구한다. 구간에는 수가 한 개 이상 들어가야 한다.

수열에서 수를 하나 제거할 수 있다. 제거하지 않아도 된다. 수를 제거하면 남은 수가 순서대로 이어져 새 수열이 되고, 구간은 이 새 수열에서 고른다.

예를 들어 수열이 10, -4, 3, 1, 5, 6, -35, 12, 21, -1이라고 하자. 수를 제거하지 않으면 12+21인 33이 가장 큰 합이다. -35를 제거하면 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 이때 10-4+3+1+5+6+12+21인 54가 가장 큰 합이다.

첫째 줄에 정수 $n$ ($1 \le n \le 100000$)이 주어진다.

둘째 줄에 수열을 이루는 $n$개의 정수가 공백으로 구분되어 주어진다. 각 수 $a_i$는 $-1000 \le a_i \le 1000$을 만족한다.

첫째 줄에 가장 큰 합을 출력한다.