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 $A_i$.
### Output
- Print $x-y$.
### Constraints
- $1 \le n \le 5000$.
- $1 \le A_i \le 10^9$.
### Example
Input:
```
4
10 80 90 30
```
Output:
```
10
```
