시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 4 1 1 33.333%

문제

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

게임이 시작하기 전에 N개의 기타 케이스가 동그랗게 놓여져있다. 각각의 케이스 안에는 기타가 들어있다.

게임이 시작하면 세준이는 케이스를 하나 고른다. 그러면 그 속에 있는 케이스에서 꺼낸다. 상대방도 마찬가지로 케이스를 하나 고르고, 기타를 케이스에서 꺼낸다. 이렇게 되면, 그룹이 2개가 생긴다. 그룹은 비어있지 않은 연속된 기타의 집합이다. 계속해서 기타를 고른다. 이 때부터는 각각의 그룹에서 기타를 하나씩 골라서 꺼내서 가져간다. 게임은 기타가 남아있지 않게 되면 끝난다.

세준이와 상대방은 고른 기타를 모두 버리지 않고 소중하게 놔두고 있다. 세준이는 세준이가 고른 기타의 가치를 최대로 만들고 싶어한다. 기타는 1번부터 N번까지 시계방향 순서대로 번호가 매겨져 있으며, N번의 바로 옆은 N-1번과 1번이다.

기타의 개수와 가치가 주어졌을 때, 세준이가고른 기타의 가치를 최대로 만드는 프로그램을 작성하시오. 세준이가 게임을 항상 먼저하며, 상대방은 완벽한 전략을 구사한다고 가정한다.

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력

5
1 5 3 4 5

예제 출력

10

힌트

출처