케이크 자르기 2

시간 제한2초메모리 제한512 MB

요약

원형 케이크에서 첫 조각을 고른 뒤 가장 큰 끝 조각을 가져가는 상대와 번갈아 끝 조각을 가져가며 합을 최대화합니다.

난이도: 보통10점 중 7점
유형: 게임 이론, 동적 계획법, 구간
정답자: 아직 제출이 없습니다

문제

JOI 군과 IOI 양은 쌍둥이 남매다. JOI 군은 요즘 과자 만들기에 푹 빠져 있어서 오늘도 케이크를 구웠다. 다 구워진 순간 냄새를 맡은 IOI 양이 찾아왔고, 두 사람은 케이크를 나눠 먹기로 했다.

케이크는 둥근 모양이다. 한 점에서 바깥쪽으로 직선으로 칼집을 넣어 케이크를 $N$ 개의 조각으로 나누고, 각 조각에 반시계 방향으로 $1$ 부터 $N$ 까지 번호를 붙인다. 즉 $1 \le i \le N$ 인 $i$ 에 대해 $i$ 번 조각은 $i-1$ 번 조각과 $i+1$ 번 조각에 붙어 있다. 여기서 $0$ 번은 $N$ 번, $N+1$ 번은 $1$ 번으로 본다. $i$ 번 조각의 크기는 $A_i$ 이고, 칼질이 서툴러 $A_i$ 는 모두 다른 값이다.

두 사람은 다음 방법으로 조각을 나눈다.

먼저 JOI 군이 $N$ 개의 조각 중 원하는 조각 하나를 가져간다.
그다음부터는 IOI 양부터 시작해 IOI 양과 JOI 군이 번갈아 남은 조각을 하나씩 가져간다. 단, 양옆 조각 중 적어도 하나가 이미 누군가에게 선택된 조각만 가져갈 수 있다. 가져갈 수 있는 조각이 여러 개면 IOI 양은 그중 가장 큰 조각을 가져가고, JOI 군은 원하는 조각을 가져갈 수 있다.

JOI 군은 자신이 가져간 조각 크기의 합을 최대로 만들고 싶다.

조각의 수 $N$ 과 각 조각의 크기가 주어질 때, JOI 군이 가져갈 수 있는 크기 합의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 조각의 수 $N$ 이 주어진다.

이어지는 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번 조각의 크기 $A_i$ 가 주어진다.

출력

JOI 군이 가져갈 수 있는 크기 합의 최댓값을 한 줄에 출력하시오.

제한

$1 \le N \le 2000$
$1 \le A_i \le 10^9$
$A_i$ 는 모두 다른 값이다.

예제4

예제 1
입력
```
5
2
8
1
10
9
```
예상 출력
```
18
```
예제 2
입력
```
8
1
10
4
5
6
2
9
3
```
예상 출력
```
26
```

예제 3

입력

예상 출력

3600242976

예제 4
입력
```
1
1000000000
```
예상 출력
```
1000000000
```