케이크 자르기 2

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$는 모두 다른 값이다.

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

1. 먼저 JOI 군이 $N$개의 조각 중 원하는 조각 하나를 가져간다.
2. 그다음부터는 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$는 모두 다른 값이다.