You are playing a game with Bruce involving coins laid out in a row.

The two players alternate taking coins from either end of the row. The game ends when no more coins remain.

Bruce is a genius and will always play optimally. However, he is nice and will let you make the first move. What is the maximum total value of coins you can take?

#### Input Specification

The first line will contain , the number of coins.

The second and final line of input will contain integers, , the values of the coins.

#### Constraints

For all subtasks,

For of points,

For of points,

#### Output Specification

The maximum total value of coins you can obtain.

#### Sample Input

```
4
4 4 9 4
```

#### Sample Output

`13`

#### Explanation for Sample Output

`4 4 9 4`

First, you take the left-most coin, with a value of .

`4 9 4`

Bruce then picks up either remaining coin, both of which have a value of .

`9 4`

Following this, you pick up the coin with a value of .

`4`

And Bruce takes the last coin, and the game ends.

Your coins have a total value of , which is the maximum value you can obtain.

## Comments

Can anybody tell me why im getting wrong answer?

The first subtask can be solved in with dynamic programming.

The second subtask uses a greedy algorithm called termity to solve in