Description

Two players, A and B, are playing a game.

Initially, there are $n$ coins in a line. From left to right, the value of the $i$-th coin is $c_i$.

A and B take turns, one move per turn. On a player's turn, they must choose the leftmost or the rightmost coin from the current sequence, remove it from the sequence, and add its value to their own total. The game ends when all coins have been taken.

Assuming both players play optimally to maximize their own total value, and player A moves first, determine the maximum total value that A can obtain.

Input Format

• The first line contains an integer $n$, the number of coins.
• Lines $2$ to $(n + 1)$ each contain one integer. The integer on line $(i + 1)$ is the value $c_i$ of the $i$-th coin.

Output Format

Output a single integer: the maximum total value that player A can obtain.

4 
30 
25 
10 
35 

60 

Hint

• Sample explanation:

  Initially, the coin sequence is $\{30,~25,~10,~35\}$.

  • Turn 1: A takes the rightmost coin, the sequence becomes $\{30,~25,~10\}$, and A’s total is $35$.
  • Turn 2: B takes the leftmost coin, the sequence becomes $\{25,~10\}$, and B’s total is $30$.
  • Turn 3: A takes the leftmost coin, the sequence becomes $\{10\}$, and A’s total is $35 + 25 = 60$.
  • Turn 4: B takes the leftmost coin, the sequence becomes empty, and B’s total is $30 + 10 = 40$. The game ends.

  The maximum total value that A can obtain is $60$.

• Constraints:

  For all testdata, $1 \leq n \leq 5 \times 10^3$, $1 \leq c_i \leq 5 \times 10^3$.

• Note: The memory limit is $64$ MiB.

Translated by ChatGPT 5