Treasure Chest

Interview

Time limit1sMemory limit128 MB

Summary

Two players alternately take a coin from either end of a row of N coins; find the maximum total the first player can guarantee with optimal play.

Level: Medium6 of 10
Topics: Dynamic programming, Game theory, Array, Intervals
Solved: No attempts yet

Problem

Bessie and Bonnie have found a treasure chest full of shiny gold coins. Being cows, though, instead of spending the coins they decide to play a game with them.

There are $N$ coins placed in a straight line, and the $i$ -th coin from the left has value $C_i$ . Bessie and Bonnie take turns. On each turn, a cow removes exactly one coin from either the left end or the right end of the line and adds that coin's value to her own total. The game ends when no coins remain.

Both cows play optimally, each trying to maximize the total value of the coins she collects, and Bessie goes first. Determine the maximum total value Bessie can guarantee for herself when both cows play optimally.

Input

The first line contains a single integer $N$ , the number of coins ( $1 \le N \le 5000$ ).

Each of the next $N$ lines contains a single integer $C_i$ , the value of the $i$ -th coin from the left ( $1 \le C_i \le 5000$ ).

Output

Print a single integer: the greatest total value Bessie can collect when both cows play optimally.

Examples3

Example 1
Input
```
4
30
25
10
35
```
Expected output
```
60
```
Example 2
Input
```
1
7
```
Expected output
```
7
```
Example 3
Input
```
3
1
100
1
```
Expected output
```
2
```