题目描述

小 A 和小 B 正在玩一个有趣的硬币游戏。

桌上有 $N$ 枚硬币排成一排，编号为 $1 \sim N$。每枚硬币有一个面值 $v_i$（正整数）。

游戏规则：

• 两人轮流操作，小 A 先手。
• 每次操作，玩家可以选择从最左边或最右边取走一枚硬币。
• 取走的硬币面值累加到该玩家的得分中。
• 游戏结束后，得分较高的玩家获胜。

假设两人都采用最优策略，请问小 A 最终能获得多少分？

输入格式

第一行输入一个整数 $N$，表示硬币数量。

第二行输入 $N$ 个整数，表示每枚硬币的面值 $v_i$。

输出格式

输出一个整数，表示小 A 在最优策略下能获得的最高分数。

样例 #1

输入

4
1 2 3 4

输出

6

样例 #2

输入

5
5 2 7 3 8

输出

15

样例说明

样例 1 说明

硬币排列：[1, 2, 3, 4]

小 A 先手选择取右边的 4，剩余 [1, 2, 3] 小 B 选择取右边的 3，剩余 [1, 2] 小 A 选择取右边的 2，剩余 [1] 小 B 取走 1

小 A 得分：4 + 2 = 6 小 B 得分：3 + 1 = 4

小 A 获胜，得分为 6。

数据范围

对于 $100\%$ 的数据，满足 $1 \le N \le 1000$，$1 \le v_i \le 10000$。

测试点编号	$N$
$1 \sim 3$	$N \le 10$
$4 \sim 7$	$N \le 100$
$8 \sim 10$	$N \le 1000$