A row of n relic tokens is laid out, each stamped with a positive integer value. Two collectors alternate turns, with the first collector going first. On a turn, a collector removes the token at either the far-left or far-right end of the current row and adds its value to their own hoard. Both play perfectly: each move is chosen to maximize the final value of that collector's own hoard, knowing the opponent does the same.
Report the margin of the first collector: the total value of the first collector's hoard minus the total value of the second collector's hoard, under optimal play by both.
Input format
Line 1: an integer n, the number of tokens.
Line 2: n space-separated positive integers, the token values from left to right.
Output format
A single integer: (first collector's total) - (second collector's total) under optimal play.
Constraints
- 1 <= n <= 200
- 1 <= each token value <= 1000