题目背景

翻译自 CSES-1097 题。

题目描述

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

现在，假设两名玩家都采取最优策略，求第一名玩家能够获得的最大得分。

输入格式

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

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

输出格式

输出一个整数，表示第一名玩家在最优策略下能获得的最大得分。

样例

4
4 5 1 3

8

说明/提示

$1 \leq n \leq 5000$；

$-10^9 \le x_i \le 10^9$。