两名海盗 Jack 和 David 刚刚截获一箱财宝，打算坐地分赃。
海盗 David 提出了一个公平的分配方案，由他来把所有的财宝排成一排，两个人轮流拿当前所有财宝左右两端，两件财宝的其中一件，直到所有的财宝都取完。
既然是 David 提出的方案，也是 David 把所有的财宝排成一排，为了公平，由 Jack 先手拿第 1 件财宝。
请编程帮助 Jack 计算出，在双方都极其聪明，都会尽可能使得自己的获利最高的前提下，Jack 最终能获得的最大收益是多少？
第 1 行输入整数 N，代表财宝的件数。
接下来 N 行读入 N 个整数，第 i 个整数 W_i 代表已经排成一排的 N 个财宝中，从左向右数第 i 件财宝的价值。
输出一个整数，代表 Jack 的最大收益。
4 7 5 20 10
27
5 7 2 4 13 7
18
12 11 13 16 9 22 21 18 22 4 4 16 18
93
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。