허브나무 | cho.sh

농부 우그네(Ugnė)는 자신의 정원에 허브나무 $N$그루를 심었습니다. 나무들은 일직선으로 심었고, 왼쪽부터 차례대로 $1$번부터 $N$번까지 번호를 매겼습니다.

그런데 첫 열매눈이 맺히자마자 우그네는 나무를 너무 빽빽하게 심었다는 것을 깨달았습니다. 이대로 두면 서로 이웃한 나무들이 서로를 가려, 올해는 열매를 하나도 거두지 못하게 됩니다.

이를 막기 위해 우그네는 일부 나무를 다른 곳으로 옮겨 심으려고 합니다. 옮겨 심은 나무는 올해 열매를 맺지 못합니다. 어떤 나무 $i$번을 그대로 남겨 두려면, 반드시 그 양옆의 나무 $i-1$번과 $i+1$번을 옮겨 심어야 합니다.

남는 열매의 총합이 최대가 되도록 하려면, 우그네는 어떤 나무들을 옮겨 심어야 할까요?

첫째 줄에 나무의 수 $N$이 주어집니다.

둘째 줄에 $N$개의 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어집니다. $A_i$는 $i$번 나무에 맺힌 열매눈의 개수입니다.

우그네가 나무를 최적으로 옮겨 심었을 때 기대할 수 있는 열매의 최대 개수를 한 줄에 하나의 정수로 출력합니다.