Optimal Strategy as Second Player

You are given a row of coins where each coin has a positive integer value. Two players take turns picking a coin from either end of the row. The first player always starts and plays optimally. Your task is to implement a program that, playing as the second player, always chooses moves that maximize your total score when both players play optimally.

Let the coin values be \(a_0, a_1, \ldots, a_{n-1}\) and the total sum be \(S = \sum_{i=0}^{n-1} a_i\). Define the dynamic programming state \(dp(i,j)\) for the current player (whose turn it is) when coins from index \(i\) to \(j\) remain. The recursive relation is given in \(\LaTeX\) as:

[ \begin{aligned} dp(i,j) &= \max\bigl(a_i - dp(i+1,j),; a_j - dp(i,j-1)\bigr)\ dp(i,i) &= a_i. \end{aligned} ]

Since the first player starts, the value \(dp(0,n-1)\) represents the maximum difference in score between the first player and the second player. Thus, the maximum total score achievable by the second player is:

[ \text{Score}_{2} = \frac{S - dp(0,n-1)}{2}. ]

You need to output this maximum score as an integer.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (the number of coins).
• The second line contains \(n\) space-separated integers \(a_0, a_1, \ldots, a_{n-1}\), representing the values of the coins.

outputFormat

Output a single integer representing the maximum total score that the second player can obtain when both players play optimally.

sample

4
4 7 2 9

6