아침 뷔페

Pär와 Oskar가 아침 뷔페에서 식사를 한다. 뷔페에는 1번부터 $N$번까지 번호가 붙은 서로 다른 $N$개의 요리가 긴 테이블에 한 줄로 놓여 있다. Pär는 요리마다 맛을 평가했고, $i$번째 요리의 점수는 $a_i$이다.

처음에 Pär가 요리 하나를 골라 먹는다. 이어서 Oskar가 요리 하나를 골라 먹는다. 둘 다 매우 배고파서, 고른 요리가 남아 있으면 그 요리를 전부 먹는다.

둘 다 먹은 뒤에는 새 요리를 고른다. 둘 다 걷기를 싫어해서, 방금 먹은 요리 바로 옆의 요리를 항상 고른다. 즉 누군가 $i$번 요리를 먹었다면 $i-1$번 또는 $i+1$번 요리를 고를 수 있다. 새로 고른 요리가 아직 남아 있으면 고른 사람이 먹는다. 이미 다 먹혔다면 그 사람은 다음 차례까지 기다려야 한다. 매 차례는 Pär가 먼저 고른다.

Pär는 까다롭게 굴지 않으려고 남아 있는 요리를 건너뛰지 않는다. 또 배가 많이 고파서 항상 최소한 한 가지는 먹고 싶어 한다. 요리를 먹은 뒤 Pär와 Oskar는 각각 "Nu är jag mätt!"라고 외치고 더 먹지 않은 채 자리를 떠날 수 있다.

아침 식사는 모든 요리가 다 먹혔거나 두 사람이 모두 자리를 떠났을 때 끝난다. Pär의 만족도는 그가 먹은 요리 점수의 합으로 정의한다.

Pär는 Oskar가 어떻게 행동할지 모른다. 그래서 Oskar의 행동에 대해 아무것도 모르는 상태에서 Pär가 자신에게 보장할 수 있는 최대 만족도를 구하려 한다.

첫 줄에 요리의 개수 $N$이 주어진다. 둘째 줄에는 $N$개의 정수가 주어지며, $i$번째 정수는 $i$번째 요리의 점수 $a_i$이다.

Pär가 보장받을 수 있는 최대 만족도를 나타내는 정수 하나를 출력한다.

$2 \le N \le 300000$

$-100 \le a_i \le 100$