과열 없는 공정 가동

문제

어느 공장의 생산 라인에는 N개의 공정이 일렬로 놓여 있고, 앞에서부터 1번, 2번, ..., N번 공정이라고 부른다. 각 공정을 하루 동안 가동하면 a_i 만큼의 이익이 생긴다. 원료비가 많이 드는 공정은 가동할수록 손해가 날 수 있으므로 a_i 는 음수일 수도 있다. 공정을 가동하지 않으면 이익도 손해도 없다. 다만 설비 과열을 막기 위해 서로 이웃한 공정 3개를 모두 가동할 수는 없다. 즉 i번, i+1번, i+2번 공정이 모두 가동되는 i 가 하나도 없어야 한다. 서로 떨어져 있는 공정은 얼마든지 함께 가동할 수 있고, 연속해서 가동하는 공정이 2개까지인 것은 허용된다. 예를 들어 이익이 3, 4, 5 인 공정이 연속해 있을 때 세 개를 모두 가동하면 12 이지만 허용되지 않으므로, 두 개만 골라야 한다. 라인 책임자는 가동할 공정을 자유롭게 고를 수 있으며, 손해만 나는 날에는 아무 공정도 가동하지 않아도 된다. 위 조건을 지키면서 얻을 수 있는 이익 합의 최댓값을 구하는 프로그램을 작성하라. 가동한 공정이 하나도 없으면 합은 0이다.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 200,000)이 주어진다. 둘째 줄에 N개의 정수 a_1, ..., a_N(-10^9 ≤ a_i ≤ 10^9)이 공백으로 구분되어 주어진다.

출력

조건을 만족하는 이익 합의 최댓값을 한 줄에 정수로 출력한다.

5
3 4 5 -1 2

11

3
-5 -2 -9

0

4
1 1 1 1

3

출처: Devin.KR 자체 제작