Sum maximization game

N cards laid out in a row from left to right. There is some integer on each card. Two players alternately take cards, one by one, and they can only take either the left or the right card of a row. The game ends when all the cards are taken (as long as there are cards, the player must do one of the possible turnes). The aim of the game is to get the biggest sum of integers, written on taken cards.

What maximum sum the first player is guaranteed to achieve through a single game?

Input

The first line contains the number of cards N (1 ≤ N ≤ 2013). The second line contains N integers (not exceeding 10^{3 }by absolute value) - the values written on the cards.

Output

Output the single number - the maximum sum the first player is guaranteed to achieve through a single game.

Examples

Note

If during the first turn player picks 1, the opponent will take either 3 or 2, in any of these cases, the first player can pick 9, and thus the sum guaranteed is 10. (After first players takes 9, the second player takes the last card, game over.)

If the first player took away 3 during the first turn, the second would take 9 in response, and eventually the maximum sum is only 3 + 2 = 5. With great folly, the second player could answer first turn with taking "1". In this case, the first player could get 3 + 9 = 12. However, the first player can not guarantee that the second will make such a stupid move; that's why the answer is not 12 but 10.