25049번 - 뮤직 플레이리스트

민규는 신우에게 $N$개의 곡이 담긴 플레이리스트를 추천받았습니다. 각 곡은 민규가 선호하는 정도 $P_i$ 를 가지고 있습니다. 물론 그 중에는 신우의 취향이 많이 들어간 곡이 있을 수도 있기 때문에, $P_i$ 는 음수 값을 가질 수 있습니다. 

민규는 플레이리스트에 있는 모든 곡들을 처음부터 순서대로 들어보려고 합니다. 민규는 싫어하는 곡을 건너뛰는 것이 플레이리스트를 선물해준 신우에 대한 예의가 아니라고 생각했기 때문에, 플레이리스트의 뒷부분으로 건너뛰는 일은 하지 않을 것입니다. 그렇지만 좋은 곡은 여러 번 듣고 싶어지는 법이기에, 최대 두 번 현재 듣고 있는 곡보다 플레이리스트 상에서 앞에 위치했던 곡으로 돌아가 그 곡부터 다시 들을 수 있습니다. 다만 민규는 뭐든지 쉽게 질려 하는 성격이기에, 같은 노래를 세 번 이상 듣게 되는 경우는 없도록 곡을 잘 건너뛸 것입니다.

선호도가 $P_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)$

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