Optimal Score for Pick-Up Game

Alice and Bob are playing a game where they take turns removing a number from either the beginning or the end of a sequence of integers. Both players play optimally. Given an array of integers, determine the maximum score that Alice can accumulate if she starts first.

Let \(dp[i][j]\) represent the maximum score Alice can secure from the subarray \(a_i, a_{i+1}, \ldots, a_j\). The recurrence is formulated as follows:

\[ dp[i][j] = \max\Bigl(a_i + \Bigl(S(i+1,j) - dp[i+1][j]\Bigr),\; a_j + \Bigl(S(i,j-1) - dp[i][j-1]\Bigr)\Bigr) \]

where \(S(l, r)\) is the sum of the elements from index \(l\) to \(r\). The final answer is given by \(dp[0][n-1]\), where \(n\) is the number of elements in the sequence.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

• The first line contains a single integer \(n\) representing the number of elements in the sequence.
• The second line contains \(n\) space-separated integers representing the sequence.

outputFormat

Output a single integer to standard output (stdout), which is the maximum score that Alice can achieve.

## sample

4
4 1 6 3

10