Alice's Maximum Sum Game

Alice and Bob are playing a game with an array of N integers. They take turns choosing an element from either the left or right end of the array. Both players play optimally in order to maximize the sum of the numbers they pick. Alice always makes the first move.

Your task is to determine the maximum sum that Alice can secure by the time the game ends.

The strategy can be derived from the following recurrence relation in terms of indices i and j (with 0-based indexing):

$$\text{dp}(i,j)= \max \Big( A[i] + \min\big(\text{dp}(i+2,j),\, \text{dp}(i+1,j-1)\big), \; A[j] + \min\big(\text{dp}(i+1,j-1),\, \text{dp}(i,j-2)\big) \Big) $$

Here, \(A[i]\) is the value of the element at index \(i\) and the \(\min\) term arises because both players play optimally.

inputFormat

The input is read from standard input (stdin) and contains two lines:

• The first line contains a single integer, N, representing the number of elements in the array.
• The second line contains N space-separated integers which represent the array A.

outputFormat

Output a single integer on standard output (stdout) — the maximum sum Alice can achieve when both players play optimally.

## sample

4
4 7 2 9

16

</p>