Optimal End-Taking Game

Two players, A and B, are playing a game with a sequence of n integers (with \(n \le 1000\)). They take turns removing numbers from the sequence, with A moving first. On each turn, a player may remove one or more consecutive numbers from either the left end or the right end (but not from both ends in the same move). The game ends when all numbers have been removed. Each player’s score is the sum of the numbers they removed. Both players are assumed to play optimally in order to maximize their own score. Your task is to compute the final score of player A.

The game can be solved using dynamic programming. Define \(dp(l, r)\) as the maximum score difference (current player’s score minus the opponent’s score) achievable when the remaining sequence is from index \(l\) to \(r\) (0-indexed). On a move, a player may choose either:

\(\bullet\) Remove the first \(k\) numbers from the left side: the contribution is \(\sum_{i=l}^{l+k-1} a_i\) minus the future difference \(dp(l+k, r)\).

\(\bullet\) Remove the last \(k\) numbers from the right side: the contribution is \(\sum_{i=r-k+1}^{r} a_i\) minus \(dp(l, r-k)\).

Thus, the recurrence is given by:

[ dp(l,r)=\max_{1\le k\le r-l+1}\Biggl{\left(\sum_{i=l}^{l+k-1}a_i - dp(l+k,r)\right), ;\left(\sum_{i=r-k+1}^{r}a_i - dp(l, r-k)\right)\Biggr} ]

with the base case \(dp(l,r)=0\) if \(l>r\). Let the total sum of the sequence be \(S\). Then, the final score of A is given by:

[ \text{A's score} = \frac{S+dp(0,n-1)}{2}. ]

</p>

inputFormat

The first line contains a single integer \(n\) \((1\le n\le 1000)\), which is the length of the sequence. The second line contains \(n\) space-separated integers representing the sequence.

outputFormat

Output a single integer, which is the final score of player A.

sample

3
1 2 3

6

</p>