예약 목록의 한 자리 조정

문제

한 병원은 하루의 예약 목록을 시간순으로 관리한다. 각 예약에는 그 예약을 별도 진료 묶음에 포함했을 때 발생하는 운영 점수가 정수로 적혀 있다. 준비 시간을 절약하는 예약은 양수 점수를 가질 수 있고, 추가 준비가 필요한 예약은 음수 점수를 가질 수 있다. 점수가 0인 예약도 있다. 점수는 이미 계산되어 있으므로 프로그램은 점수가 만들어진 이유를 고려하지 않는다. 담당자는 예약 목록에서 연속한 구간 하나를 골라 집중 진료 묶음을 만들려 한다. 구간을 고른 뒤에는 그 안의 예약을 최대 하나까지 다른 진료실로 옮길 수 있다. 옮긴 예약의 점수는 묶음 점수에서 제외한다. 예약을 전혀 옮기지 않아도 된다. 선택한 구간 밖의 예약을 새로 포함하거나, 구간 안에서 둘 이상의 예약을 옮길 수는 없다. 최종 묶음에는 예약이 적어도 하나 남아 있어야 한다. 따라서 길이가 1인 구간을 선택했다면 그 예약을 옮길 수 없다. 중간 예약 하나를 옮겼을 때 양쪽에 남은 예약들은 하나의 묶음으로 취급한다. 원래 구간의 양 끝에 있는 예약을 옮기는 것도 허용한다. 묶음 점수는 최종적으로 남은 모든 예약의 점수를 더한 값이다. 담당자의 목표는 묶음 점수를 가능한 한 크게 만드는 것이다. 모든 예약의 점수가 음수여도 빈 묶음을 만들 수 없으므로 정답이 음수가 될 수 있다. 같은 최대 점수를 만드는 선택이 여러 개라면 어느 구간을 골랐는지 구분하지 않으며, 최대 점수만 출력한다. 주어진 예약 순서를 바꾸지 않고 이 규칙으로 얻을 수 있는 최대 묶음 점수를 구한다.

입력

첫째 줄에 예약 수 N이 주어진다. 1 ≤ N ≤ 60,000이다.
둘째 줄에 시간순으로 나열한 예약 점수 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다. 각 점수는 -100 이상 100 이하의 정수다.

출력

규칙에 따라 얻을 수 있는 최대 묶음 점수를 정수 하나로 출력한다.

6
4 -7 3 5 -2 1

12

4
-8 -3 -6 -4

-3

1
0

0

출처: Devin.KR 자체 제작