Hocolate Hame

Time limit2sMemory limit2048 MB

Summary

Two players eat a row of pieces from opposite ends, each move taking k or k+1 pieces, and the task is the optimal sweetness difference between them.

Level: Medium6 of 10
Topics: Dynamic programming, Prefix sum, Game theory
Solved: No attempts yet

Problem

Azizkhan and Temirulan love Swiss chocolate. Recently they bought a chocolate bar made of a row of $n$ pieces. Each piece has a certain amount of sweetness, and the sweetness can be negative. The pieces are numbered $1, 2, \ldots, n$ from left to right. Azizkhan eats from the left side and Temirulan eats from the right side, taking turns. Each player eats one or more pieces per turn. Azizkhan goes first and can eat either 1 or 2 pieces. If $k$ pieces were eaten on the previous move, the current player must eat either $k$ or $k + 1$ pieces. They stop when the next move is impossible. Each player wants to eat more sweetness than the other, so each player tries to maximize the difference between the total sweetness of the pieces he ate and the total sweetness of the pieces the opponent ate. Find the difference between the total sweetness consumed by Azizkhan and the total sweetness consumed by Temirulan if both play optimally.

Input

The first line contains an integer $n$ ( $1 \le n \le 4000$ ), the number of pieces. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $-10^4 \le a_i \le 10^4$ ), the sweetness values of the pieces.

Output

Output a single integer: the difference between the total sweetness consumed by Azizkhan and the total sweetness consumed by Temirulan if both play optimally.

Examples2

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
-3
```
Example 2
Input
```
6
-2 5 100 6 3 4
```
Expected output
```
90
```