1496번 - 기타 고르기

세준이는 상대방과 자유로운 기타 연주 대결을 벌이는 TV 쇼에 나갔다.

게임이 시작하기 전에 N개의 기타 케이스가 원형으로 놓여져 있다. (1 ≤ i < N에 대해 i번째 기타 케이스와 i+1번째 기타 케이스는 서로 인접해 있고, N번째와 1번째 기타 케이스도 인접해 있다.) 각각의 케이스 안에는 기타가 들어있다.

세준이와 상대방은 번갈아가며 기타를 가져간다. 두 사람은 각자의 차례에 모든 그룹에서 기타를 하나씩 골라서 꺼내 가져간다. 그룹이란 비어있지 않은 연속한 기타의 집합이다. 기타를 꺼낼 때마다, 그룹이 새로 생길 수도, 사라질 수도 있다.

이해를 돕기 위해, 다음과 같은 게임 진행을 생각해 보자. 

0. N = 8, 게임 시작 전 → 현재 남은 그룹: (1,2,3,4,5,6,7,8)
1. 세준이가 2번 기타를 가져감 → 현재 남은 그룹: (1,3,4,5,6,7,8)
2. 상대방이 7번 기타를 가져감 → 현재 남은 그룹: (1,8) (3,4,5,6)
3. 세준이가 1, 4번 기타를 가져감 → 현재 남은 그룹: (8) (3) (5,6)
4. 상대방이 3, 5, 8번 기타를 가져감 → 현재 그룹: (6)
5. 세준이가 6번 기타를 가져감 → 현재 그룹: 
6. 남은 기타가 없으므로 게임이 종료됨

세준이와 상대방은 고른 기타를 모두 버리지 않고 소중하게 놔두고 있다. 세준이는 세준이가 고른 기타의 가치의 합을 최대로 만들고 싶어한다. 기타의 개수와 가치가 주어졌을 때, 세준이가 고른 기타들의 가치의 합을 최대로 만드는 프로그램을 작성하시오. 게임은 항상 세준이가 먼저 시작하며, 두 사람은 최적의 전략을 구사한다고 가정한다.

첫째 줄에 기타의 개수 N이 주어진다. 기타의 개수는 50보다 작거나 같으며, 2보다 크거나 같은 자연수이다. 둘째 줄에 기타의 가치가 주어진다. 기타의 가치는 공백을 사이에 두고 구분해서 순서대로 주어지며, 10,000보다 작거나 같은 자연수이다.

첫째 줄에 답을 출력한다.