Charlie and the Optimal Game

In this problem, Charlie and Dave are playing a game with a row of cards. Each card has a positive integer value. The players take turns picking one card from either end of the row, and both play optimally. Charlie starts first. Your task is to determine the maximum sum of card values that Charlie can obtain.

Formally, you are given an array of N integers where each integer represents the value on a card. In each turn, a player picks a card from either the left or right end of the array. The game continues until all cards are taken. Under optimal play, the decision process can be modeled using dynamic programming with the recurrence: [ \text{dp}[i][j] = \max \Big( a_i + \min(\text{dp}[i+2][j],,\text{dp}[i+1][j-1]),\quad a_j + \min(\text{dp}[i+1][j-1],,\text{dp}[i][j-2]) \Big) ] where $a_i$ is the value at index $i$ (0-indexed).

Output the maximum sum that Charlie can guarantee if he follows an optimal strategy.

inputFormat

The input is read from stdin. The first line contains an integer N, the number of cards. The second line contains N space-separated integers representing the card values.

outputFormat

Print a single integer—the maximum sum that Charlie can secure under optimal play—to stdout.## sample

4
1 2 9 4

10