망원경 냉각 시간표

문제

산속 천문대는 한 대의 망원경으로 밤하늘을 관측한다. 오늘 밤의 운영 시간은 길이가 같은 N개의 시간 칸으로 나누어져 있으며, 시간순으로 1번부터 N번까지 번호가 붙어 있다. 천문대는 각 시간 칸에 관측을 수행했을 때 얻을 수 있는 자료의 가치를 미리 계산했다. 이 값은 구름의 양과 관측 대상의 위치를 반영한 정수이며, 관측 조건이 나쁜 시간에는 음수가 될 수도 있다. 망원경은 한 시간 칸 동안 관측을 수행하면 바로 다음 시간 칸 전체를 냉각에 사용해야 한다. 냉각 중에는 관측할 수 없으므로, 번호가 연속한 두 시간 칸을 모두 관측 시간으로 선택할 수 없다. 한 칸 이상을 비워 두었다면 그 뒤에는 다시 관측할 수 있다. 관측하지 않는 시간에는 별도의 자료 가치가 생기지 않으며, 냉각을 위한 추가 비용도 없다. 첫 번째 시간 칸이 시작되기 전에는 망원경이 충분히 냉각되어 있다고 가정한다. 천문대는 각 시간 칸을 통째로 관측하거나 관측하지 않아야 한다. 한 시간 칸을 나누어 일부만 관측할 수 없고, 다른 시간 칸으로 관측을 옮길 수도 없다. 마지막 시간 칸을 관측한 경우 그 뒤의 냉각 시간은 오늘 밤의 운영 시간에 포함되지 않으므로 별도로 고려하지 않는다. 선택한 시간 칸들의 자료 가치를 모두 더한 값이 오늘 얻는 총가치가 된다. 운영자는 냉각 규칙을 지키면서 총가치가 가장 커지는 시간표를 만들려고 한다. 관측을 한 번도 하지 않는 시간표도 허용하며, 이때 총가치는 0이다. 따라서 모든 관측 조건이 나쁘다면 아무것도 관측하지 않는 것이 최선일 수 있다. 각 시간 칸의 자료 가치가 주어질 때 가능한 총가치의 최댓값을 구한다. 같은 최댓값을 만드는 시간표가 여러 개라도 관측 횟수나 선택한 시간 칸의 번호는 비교하지 않으며, 최댓값만 출력한다.

입력

첫째 줄에 시간 칸의 개수 N이 주어진다. 둘째 줄에 각 시간 칸의 자료 가치 V_1, V_2, ..., V_N이 공백으로 주어진다.
1 ≤ N ≤ 30,000
-100,000 ≤ V_i ≤ 100,000
입력의 모든 수는 정수이다.

출력

냉각 규칙을 지키는 시간표로 얻을 수 있는 총가치의 최댓값을 한 줄에 출력한다. 관측할 시간 칸을 선택하지 않는 경우의 총가치는 0이다.

6
8 12 7 -3 10 9

25

4
-5 -2 -8 -1

0

1
17

17

출처: Devin.KR 자체 제작