题目描述

有一排 $n$ 个数，两名玩家轮流操作。每次操作，当前玩家从这一排的最左端或最右端取走一个数，他的得分加上这个数。两名玩家都想让自己的得分尽可能大。

如果两人都采取最优策略，先手最多能得多少分？

输入格式

第一行一个整数 $n$，表示数的个数。

第二行 $n$ 个整数 $x_1, x_2, \dots, x_n$。

输出格式

输出一个整数，表示先手的最大得分。

输入样例

4
4 5 1 3

输出样例

8

说明

先手取 3，后手只能取 4 或 1：后手取 4，先手取 5，后手取 1；先手共 3 + 5 = 8 分。

数据范围

$1 \le n \le 5000$，$-10^9 \le x_i \le 10^9$。

来源：CSES 1097 Removal Game。