Optimal Card Game Strategy

Sara and her opponent are playing a card game in which a row of cards is laid out, each card having a certain score value. Players take turns picking a card from either end of the row. Both players play optimally, meaning that each player maximizes their own eventual score. Given the list of card scores, determine the maximum score that Sara can achieve.

The strategy involves dynamic programming to simulate the optimal moves by both players. The recurrence relation is based on choosing the leftmost or rightmost card and then considering the opponent's optimal counterplay.

It is guaranteed that there is at least one card. The challenge is to compute the maximum score Sara can achieve from the given card arrangement.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10³) representing the number of cards. The second line contains n space-separated integers, each representing the score value of a card.

outputFormat

Output a single integer — the maximum score that Sara can achieve when both players play optimally.

## sample

4
1 2 9 4

10

</p>