Optimal Candy Picking Game

Alice and Bob are playing a game with a row of candies. There are n candies arranged in a line, and each candy has a positive integer value. In each turn, a player can pick a candy from either end of the row. Both players play optimally to maximize their own scores.

Your task is to determine the maximum total score Alice can achieve if she starts the game and both players make optimal moves. Formally, given an integer n and a list candies of length n where each element represents the value of a candy, compute the maximum score Alice can secure.

The decision process follows the minimax strategy. When Alice picks a candy, Bob will then choose a move that minimizes Alice's future gain, and vice versa. The recurrence relation for the optimal score can be expressed in LaTeX as follows:

$$\text{dp}(i,j)= \max\Bigl( candy[i] + \min\{ dp(i+2,j),\; dp(i+1,j-1) \},\; candy[j] + \min\{ dp(i+1,j-1),\; dp(i,j-2) \} \Bigr), $$

with the base condition:

$$dp(i,i)= candy[i].$$

Compute and output the maximum score for Alice.

inputFormat

The input is read from standard input and contains two lines:

• The first line contains a single integer n (1 ≤ n ≤ 1000) representing the number of candies.
• The second line contains n space-separated positive integers, where the i-th integer denotes the value of the i-th candy.

outputFormat

Output a single integer to standard output — the maximum score Alice can achieve if both players play optimally.

## sample

6
1 2 9 4 4 6

16

</p>