뮤직 플레이리스트

민규는 신우에게 $N$개의 곡이 담긴 플레이리스트를 추천받았습니다. 각 곡에는 민규가 선호하는 정도 $P_i$가 있습니다. 신우의 취향이 많이 반영된 곡은 $P_i$가 음수일 수 있습니다.

민규는 플레이리스트의 곡을 처음부터 순서대로 듣습니다. 싫어하는 곡을 건너뛰는 것은 플레이리스트를 선물한 신우에게 예의가 아니라고 생각하므로, 뒤쪽 곡으로 건너뛰지는 않습니다. 대신 좋은 곡은 다시 듣고 싶으므로, 현재 듣고 있는 곡보다 앞에 있던 곡으로 최대 두 번 돌아가 그 곡부터 다시 들을 수 있습니다. 다만 같은 노래를 세 번 이상 듣게 되는 경우는 없도록 곡을 잘 건너뛰어야 합니다.

곡 $i$를 들으면 민규의 만족도가 $P_i$만큼 올라갑니다. 민규가 플레이리스트를 가장 만족스럽게 들었을 때의 만족도를 구하세요.

첫 번째 줄에 곡의 개수 $N$이 주어집니다. $(2 \le N \le 5 \times 10^5)$

두 번째 줄에 $N$개의 정수 $P_1, P_2, P_3, ..., P_N$이 공백으로 구분되어 주어집니다. $(-10^9 \le P_i \le 10^9)$

첫 번째 줄에 민규가 얻을 수 있는 최대 만족도를 출력합니다.