서버의 보너스 작업 시간

문제

게임 서버의 운영자는 정규 서비스 사이에 실행할 보너스 작업 일정을 정하고 있다. 오늘 사용할 수 있는 시간은 같은 길이의 N개 구간으로 나뉘며, 시간순으로 1번부터 N번까지 번호가 붙어 있다. 각 구간에는 그 구간에서만 실행할 수 있는 보너스 작업이 하나 준비되어 있다. 운영자는 각 작업을 실행하거나 건너뛰는 선택을 할 수 있다. 작업 하나는 해당 구간 전체를 사용하고 다른 구간으로 옮길 수 없다. i번 작업을 실행했을 때 얻는 순기여도는 정수 A_i이다. 순기여도에는 보상과 처리 비용이 함께 반영되어 있으므로 음수일 수도 있다. 작업을 건너뛰면 그 구간의 기여도는 0이다. 선택한 일정의 총기여도는 실행한 모든 작업의 순기여도를 더한 값으로 정의한다. 서버의 부하를 낮추기 위해 보너스 작업을 세 구간 연속으로 실행하는 것은 금지한다. 즉, 1 ≤ i ≤ N-2인 어떤 i에 대해서도 i번, i+1번, i+2번 작업을 모두 실행할 수 없다. 두 구간 연속으로 실행하는 것은 허용되며, 한 구간을 건너뛰면 그 앞뒤에서 실행한 작업은 연속으로 세지 않는다. 정규 서비스는 별도 자원에서 처리되므로 이 규칙 외에 추가로 고려할 제한은 없다. 첫 구간 이전과 마지막 구간 이후에는 보너스 작업이 없다. 또한 아무 작업도 실행하지 않는 일정도 허용하며, 그 일정의 총기여도는 0이다. 따라서 모든 작업의 순기여도가 음수여도 유효한 일정을 만들 수 있다. 최적 일정이 여러 개라면 그중 어느 일정을 선택하는지는 중요하지 않으며, 달성할 수 있는 총기여도의 최댓값만 구한다. 시간순으로 주어진 작업 정보를 이용해 이 값을 계산하는 프로그램을 작성한다.

입력

첫째 줄에 시간 구간 수 N이 주어진다. 1 ≤ N ≤ 50,000이다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. -999 ≤ A_i ≤ 999이다.

출력

세 구간 연속 실행을 피하면서 얻을 수 있는 총기여도의 최댓값을 정수 하나로 출력한다. 실행할 작업을 하나도 선택하지 않는 경우의 값은 0이다.

6
5 8 6 -4 7 9

30

4
-3 -1 -8 -2

0

3
4 4 4

8

출처: Devin.KR 자체 제작