Choosing Guitars

Sejun is playing a guitar-picking game against an opponent.

Before the game starts, N guitar cases are arranged in a circle. Each case contains one guitar. For each i with 1 <= i < N, case i is adjacent to case i+1, and case N is also adjacent to case 1.

A group is a nonempty consecutive set of guitars that have not been taken yet. On every turn, the current player must choose and take exactly one guitar from every remaining group. When a guitar is taken, the group containing it may split into the remaining consecutive parts on its left and right; empty parts are not groups.

For example, when N = 8, one possible game can proceed as follows.

1. Before any move, the remaining group is (1,2,3,4,5,6,7,8).
2. Sejun takes guitar 2 -> remaining group: (1,3,4,5,6,7,8).
3. The opponent takes guitar 7 -> remaining groups: (1,8), (3,4,5,6).
4. Sejun takes guitars 1 and 4 -> remaining groups: (8), (3), (5,6).
5. The opponent takes guitars 3, 5, and 8 -> remaining group: (6).
6. Sejun takes guitar 6 -> no guitars remain.
7. The game ends because there are no remaining guitars.

Both players keep all guitars they take. Sejun wants to maximize the total value of the guitars he takes. Given the number of guitars and their values, compute the maximum total value Sejun can obtain when he moves first and both players play optimally.

The first line contains the number of guitars N. N is a natural number between 2 and 50, inclusive.

The second line contains N guitar values in circular order. Each value is a natural number between 1 and 10,000, inclusive, and the values are separated by spaces.

Print the maximum possible total value of the guitars Sejun can obtain.