Consider a row of ~N~ coins of values ~V_1 . . . V_n~. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.

Note: The opponent is as clever as the user.

Input

• The first line contains an integer ~N~ - the number of coins ~(N \leq 10^3)~.

• In the next line contains ~N~ numbers which are coin values.

  Output

• Print the maximum amount of money.

Sample Input 1

4
5 3 7 10

Sample Output 1

15

Sample Input 2

4
8 15 3 7

Sample Output 2

22