Treasure Coins Game

Bessie and Bonnie have discovered a treasure chest containing n gold coins arranged in a line. The value of the i-th coin is given by \(c_i\) (with \(1 \leq c_i \leq 5000\)). Two players, A and B, take turns picking coins from either end of the line. In each turn, the current player removes exactly one coin from either the leftmost or rightmost end and adds its value to her/his total. The game terminates when all coins have been taken.

Both players play optimally to maximize their cumulative wealth. Player A moves first. Your task is to compute the maximum total value that player A can collect.

Input Constraints:

• \(1 \leq n \leq 5000\)
• \(1 \leq c_i \leq 5000\)

Hint: One standard approach is to use dynamic programming with a state \(dp[i][j]\) representing the maximum difference in the score (current player's score minus the opponent's score) that can be achieved from the subarray of coins indexed from \(i\) to \(j\). The recurrence is:

[ \text{dp}[i][j] = \max\left(c_i - \text{dp}[i+1][j],; c_j - \text{dp}[i][j-1]\right). ]

Once \(\text{dp}[0][n-1]\) is computed and the total sum \(S\) of all coins is known, the maximum total for player A is given by:

[ \text{Answer} = \frac{S + \text{dp}[0][n-1]}{2}. ]

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) representing the number of coins.
• The second line contains \(n\) space-separated integers \(c_1, c_2, \ldots, c_n\) indicating the value of each coin.

outputFormat

Output a single integer: the maximum total value that player A can accumulate when both players play optimally.

sample

4
30 25 10 35

60

</p>