题目描述

有一个包含 $n$ 个数字的列表，两名玩家轮流进行操作。在每一步中，当前玩家可以从列表的开头或末尾移除一个数字，并将该数字的值加入到自己的得分中。两名玩家都会采取最优策略，尽可能使自己获得的总得分最大化。

现在，假设你是先手玩家，请你计算在两名玩家都采取最优策略的情况下，你能获得的最大得分。

输入格式

第一行包含一个整数 $n$，代表列表的大小。

第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$，代表列表中的数字。

输出格式

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

样例

4
4 5 1 3

8

数据范围

• $1 \le n \le 5000$
• $-10^9 \le x_i \le 10^9$