기타 고르기

세준이는 상대와 기타 연주 대결을 하는 게임에 참가했다.

게임이 시작되기 전, N개의 기타 케이스가 원형으로 놓여 있다. 각 케이스에는 기타가 하나씩 들어 있다. 1 <= i < N인 i에 대해 i번째 케이스와 i+1번째 케이스는 서로 이웃하고, N번째 케이스와 1번째 케이스도 서로 이웃한다.

아직 가져가지 않은 기타들이 원 위에서 연속해 있으면 하나의 그룹이다. 매 차례 현재 플레이어는 남아 있는 모든 그룹마다 기타 하나를 골라 가져가야 한다. 어떤 기타를 가져가면 그 기타가 속한 그룹은 왼쪽과 오른쪽의 남은 연속 구간으로 나뉠 수 있고, 빈 구간은 그룹이 아니다.

이해를 돕기 위해 N = 8일 때 다음과 같은 진행을 생각해 보자.

1. 시작 전 남은 그룹: (1,2,3,4,5,6,7,8)
2. 세준이가 2번 기타를 가져감 -> 남은 그룹: (1,3,4,5,6,7,8)
3. 상대가 7번 기타를 가져감 -> 남은 그룹: (1,8), (3,4,5,6)
4. 세준이가 1번과 4번 기타를 가져감 -> 남은 그룹: (8), (3), (5,6)
5. 상대가 3번, 5번, 8번 기타를 가져감 -> 남은 그룹: (6)
6. 세준이가 6번 기타를 가져감 -> 남은 그룹 없음
7. 남은 기타가 없으므로 게임이 끝난다.

두 사람은 자신이 가져간 기타를 모두 보관한다. 세준이는 자신이 가져간 기타 가치의 합을 최대화하려고 한다. 기타의 개수와 각 기타의 가치가 주어질 때, 세준이가 먼저 시작하고 두 사람이 모두 최적으로 플레이한다고 가정하여 세준이가 얻을 수 있는 가치 합의 최댓값을 구하라.

첫째 줄에 기타의 개수 N이 주어진다. N은 2 이상 50 이하인 자연수이다.

둘째 줄에는 각 기타의 가치 N개가 원형 순서대로 주어진다. 각 가치는 1 이상 10,000 이하인 자연수이며, 공백으로 구분된다.

세준이가 얻을 수 있는 기타 가치 합의 최댓값을 출력한다.