There are a bunch of coins on a table, laid out in a straight line.
Each coin has a (positive) value from $1$ to $1000$. Now, you're going to play a game with a friend.

At every turn, you must remove a coin from one end of the line.
Turns alternate, so your friend goes immediately after you're done.
The game ends when there are no coins remaining.

An example game:
The coins start like this:
$4,4,9,4$
You always go first, so you take the $4$ from the left side:
$4,9,4$
Your friend takes any of the $4$s (it doesn't matter)
$9,4$
Now you can take the $9$, and your friend takes the remaining $4$.

Your score, in this case, is $4+9=13$.
(In this case, you can always beat your friend.)
Find the maximum possible score you can achieve.

Input Specification

$N\le 1000$, the number of coins.
$N$ lines, each with the value of a coin.

Output Specification

Your maximum possible score, provided that you go first and your friend plays perfectly.