아침 식사 뷔페

페르와 오스카르는 아침 식사 뷔페를 먹으려고 한다. 뷔페는 $1$부터 $N$까지 번호가 매겨진 서로 다른 $N$개의 요리로 이루어져 있다. 이 요리들은 긴 테이블 위에 한 줄로 놓여 있다. 페르는 어떤 요리가 다른 요리보다 더 맛있다고 생각한다. 그래서 각 요리의 맛을 나타내는 점수를 매겼다. $i$번째 요리의 점수는 $a_i$이다.

처음에 페르가 요리 하나를 골라 먹는다. 그다음 오스카르가 요리 하나를 골라 먹는다. 둘 다 매우 배가 고프므로 자신이 고른 요리는 언제나 남김없이 모두 먹는다.

둘 다 다 먹고 나면 새로운 요리를 고를 수 있다. 페르와 오스카르는 걷는 것을 귀찮아하므로 언제나 방금 먹은 요리의 바로 옆에 있는 요리를 고른다. 즉, 누군가 방금 $i$번 요리를 먹었다면 $i-1$번 요리 또는 $i+1$번 요리를 고를 수 있다. 새로 고른 요리가 아직 먹히지 않았다면, 그 요리를 고른 사람이 가져가서 먹는다. 이미 먹힌 요리라면 그 사람은 다음 차례까지 기다려야 한다. 매 차례에는 페르가 먼저 고른다.

페르는 까다롭게 굴고 싶지 않으므로, 남아 있는 요리를 먹지 않고 지나가지는 않을 것이다. 또한 앞서 말했듯이 매우 배가 고프므로 항상 적어도 하나의 요리는 먹으려고 한다. 페르와 오스카르는 모두 요리를 하나 먹은 뒤 큰 소리로 "이제 배불러!"라고 외치고 더는 아무것도 먹지 않은 채 아침 식사를 떠날 수 있다.

모든 요리가 먹혔거나 둘 다 아침 식사를 떠나면 식사가 끝난다. 페르의 만족도는 자신이 먹은 요리들이 얼마나 맛있는지에 따라 달라진다. 그의 만족도를 그가 먹은 모든 요리의 점수 합으로 정의한다.

페르는 오스카르가 어떻게 행동할지 잘 모른다. 따라서 오스카르의 행동에 관해 아무것도 모르는 상태에서 자신이 보장할 수 있는 최대 만족도를 알고 싶다.

점수

여러 테스트 케이스 그룹으로 풀이를 평가한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$25$| $2 \le N \le 100$, $0 \le a_i \le 100$

$2$ |$25$| $2 \le N \le 1000$, $0 \le a_i \le 100$

$3$ |$25$| $0 \le a_i \le 100$

$4$ |$25$| 추가 제한 없음

첫째 줄에 뷔페의 요리 수를 나타내는 정수 $N$ ($2 \leq N \leq 3*10^5$)이 주어진다. 그다음 줄에 $N$개의 정수 $a_1, a_2, \ldots, a_i$ ($-100 \leq a_i \leq 100$)가 주어지며, 이는 $i$번째 요리의 맛을 나타낸다.

프로그램은 페르가 얻는다고 보장할 수 있는 최대 만족도를 나타내는 정수 하나를 출력해야 한다.

예제 1

페르가 $3$ 또는 $2$를 주는 요리 중 하나를 먹는 것으로 시작하면 오스카르가 나머지 음식을 모두 먹을 수 있다. 따라서 페르는 대신 가운데에서 시작하려 하며, 그러면 만족도 $7$을 보장할 수 있다.

예제 2

여기서는 페르가 5를 주는 요리를 먼저 고르는 것이 가장 좋다. 오스카르가 어느 쪽에서 시작하느냐에 따라 페르는 만족도 8 또는 9를 얻을 수 있으므로, 8를 보장받는다.

예제 3

마지막 테스트 케이스 그룹에서는 요리가 맛없어서 음의 만족도를 줄 수도 있다. 여기에서도 페르는 5를 주는 요리에서 시작하는 것이 가장 좋다. 오스카르가 그의 왼쪽에서 시작하면 페르는 -1을 주는 요리를 먹은 다음 2를 주는 요리를 먹어 총 만족도 6을 얻을 수 있다. 오스카르가 그의 오른쪽에서 시작하면 페르는 -2와 3을 먹은 다음 만족한 상태로 떠날 수 있으며, 이때도 총 만족도는 6이다.

예제 4

여기서는 모든 요리가 맛없지만, 페르는 그래도 무언가를 먹어야 한다. 따라서 가장 덜 맛없는 요리를 골라 만족도 -1을 얻는다.