10081 연속합 2 Gold IV

문제

N개의 정수로 이루어진 수열에서 최대 하나의 수를 제거할 수 있을 때, 연속된 부분수열의 합 중 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에 N개의 정수가 주어진다. 각 정수는 절댓값이 1,000 이하이다.

출력

최대 구간 합을 출력한다.

10
10 -4 3 1 5 6 -35 12 21 -1

54