수조 청소 계획

문제

수족관의 한 전시실에 수조가 일렬로 N개 놓여 있다. 왼쪽부터 i번째 수조를 청소하면 a_i점을 얻는다. 청소 과정에서 물고기가 스트레스를 받아 손해가 생기는 수조는 a_i가 음수이고, 청소해도 얻는 것이 없는 수조는 a_i가 0이다. 관리자는 청소할 수조를 마음대로 고를 수 있다. 다만 안전 규정 때문에 서로 이웃한 세 수조를 모두 청소할 수는 없다. 즉 어떤 i에 대해서도 i번, i+1번, i+2번 수조가 동시에 선택되어서는 안 된다. 이웃한 두 수조를 함께 청소하는 것은 허용되고, 떨어져 있는 수조를 고르는 것은 아무 제한이 없다. 아무 수조도 청소하지 않아도 되며, 이 경우 점수의 합은 0이다. 규정을 지키면서 선택한 수조의 점수 합을 최대로 만들었을 때, 그 최댓값을 구하는 프로그램을 작성하라. 점수의 합이 가장 큰 선택이 여러 가지여도 출력하는 것은 합의 값 하나뿐이다. 모든 a_i가 음수이면 아무것도 고르지 않는 것이 최선이므로 답은 0이다.

입력

첫 줄에 수조의 수 N이 주어진다. (1 ≤ N ≤ 60,000) 둘째 줄에 a_1, a_2, ..., a_N이 공백으로 구분되어 주어진다. 각 a_i는 정수이며 -999 ≤ a_i ≤ 999이다.

출력

규정을 지키며 얻을 수 있는 점수 합의 최댓값을 정수 하나로 출력한다.

6
5 4 -3 6 7 -1

22

3
-5 -2 -9

0

3
1 2 3

5

출처: Devin.KR 자체 제작