Two players are playing a game. They have been given a array of numbers (Array A). Player 1 starts by picking any number.

A player may choose any number adjacent to other player's last pick. If no such number exists, he can choose any number from the remaining unchosen ones. You cannot pick a number which has already been picked by any player.

The two players pick numbers alternatively. Assume both the players play optimally.

The score of a players is the sum of the numbers he has chosen. What is the maximum score Player1 can obtain?

Constraints:

2 <= length of A <= 100000

1 <= A[i] <= 1000

Example:

|A| = 5;

A = {40, 200, 20, 15, 20}

Answer: 240.

Explanation: Player1 chooses 200. Payers2 chooses 40 (among 40 and 20). Player1 chooses 20 (among 20, 15, 20), Player2 chooses 15 (he's only choice). Player1 chooses 20 (last array element).