Marisa and Reimu are playing a game on an array A of n integers. Starting from Marisa, they take turns performing the following move:
- Pick either the first or the last element in array A and remove it. The player gain x points, where x is the previously chosen element.
Let x and y are the score of Marisa and Reimu at the end of the game, respectively. Marisa wants to maximize x−y while Reimu wants to minimize x−y.
Assuming they both play optimally, find the resulting x−y.
### Input
- The first line contains an integer n.
- The second line contains n integers Ai.
### Output
- Print x−y.
### Constraints
- 1≤n≤5000.
- 1≤Ai≤109.
### Example
Input:
410809030
Output:
10