There are a bunch of coins on a table, laid out in a straight line.

Each coin has a (positive) value from to . 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:

You always go first, so you take the from the left side:

Your friend takes any of the s (it doesn't matter)

Now you can take the , and your friend takes the remaining .

Your score, in this case, is .

(In this case, you can always beat your friend.)

Find the maximum possible score you can achieve.

#### Input Specification

, the number of coins.

lines, each with the value of a coin.

#### Output Specification

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

## Comments