题目描述

有一个包含 $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$