题目描述

两名海盗 $Jack$ 和 $David$ 刚刚截获一箱财宝，打算坐地分赃。

海盗 $David$ 提出了一个公平的分配方案，由他来把所有的财宝排成一排，两个人轮流拿当前所有财宝左右两端，两件财宝的其中一件，直到所有的财宝都取完。

既然是 $David$ 提出的方案，也是 $David$ 把所有的财宝排成一排，为了公平，由 $Jack$ 先手拿第 $1$ 件财宝。

请编程帮助 $Jack$ 计算出，在双方都极其聪明，都会尽可能使得自己的获利最高的前提下，$Jack$ 最终能获得的最大收益是多少？

输入格式

第 $1$ 行输入整数 $N$，代表财宝的件数。

接下来 $N$ 行读入 $N$ 个整数，第 $i$ 个整数 $W_i$ 代表已经排成一排的 $N$ 个财宝中，从左向右数第 $i$ 件财宝的价值。

输出格式

输出一个整数，代表 $Jack$ 的最大收益。

样例输入 #1

4
7
5
20
10

样例输出 #1

27

样例输入 #2

5
7
2
4
13
7

样例输出 #2

18

样例输入 #3

12
11
13
16
9
22
21
18
22
4
4
16
18

样例输出 #3

93

数据范围

样例 $1$ 解释

$Jack$ 拿最左侧价值为 $7$ 的财宝，剩余财宝有： $5$ $20$ $10$。

$David$ 拿最后侧价值为 $10$ 的财宝，剩余财宝有 $5$ $20$。

$Jack$ 拿最右侧价值为 $20$ 的财宝，剩余财宝有 $5$。

$David$ 拿走最后一个价值为 $5$ 的财宝。

该方案为 $Jack$ 最大收益的方案，$Jack$ 的最大收益为 $7+20=27$。

数据范围

对于 $40\%$ 的数据，$1 \le N \le 20$。

对于 $100\%$ 的数据，$1 \le N \le 5 \times 10^3$，$1 \le W_i \le 5 \times 10^3$。