题目描述

Bessie and Bonnie have found a treasure chest full of marvelous gold coins! Being cows, though, they can't just walk into a store and buy stuff, so instead they decide to have some fun with the coins.

The N (1 <= N <= 5,000) coins, each with some value C_i (1 <= C_i <= 5,000) are placed in a straight line. Bessie and Bonnie take turns, and for each cow's turn, she takes exactly one coin off of either the left end or the right end of the line. The game ends when there are no coins left.

Bessie and Bonnie are each trying to get as much wealth as possible for themselves. Bessie goes first. Help her figure out the maximum value she can win, assuming that both cows play optimally.

Consider a game in which four coins are lined up with these values:

30 25 10 35

Consider this game sequence:

Bessie Bonnie New Coin

Player Side CoinValue Total Total Line

Bessie Right 35 35 0 30 25 10

Bonnie Left 30 35 30 25 10

Bessie Left 25 60 30 10

Bonnie Right 10 60 40 --

This is the best game Bessie can play.

小 A 和小 B 在玩游戏。

初始时，有 $n$ 个硬币被摆成了一行，从左至右数第 $i$ 个硬币的价值为 $c_i$。

小 A 和小 B 每人一回合，在一个人的回合中，他可以选择当前硬币序列最左侧或者最右侧的硬币，并将他从序列中取出，将其价值累加到自己获得的累计价值中，然后进行另一个人的回合。当硬币全部被取走时，游戏结束。

请求出在双方都尽可能的使自己累计价值最大的情况下，若由小 A 进行第一回合，那么他能获得的累计价值最大是多少。

输入格式

输入的第一行是一个整数 $n$，代表硬币的个数。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 个硬币的价值 $c_i$。

输出格式

输出一行一个整数，代表小 A 能获得的最大累计价值。

4 
30 
25 
10 
35 

60 

提示

输入输出样例 $1$ 解释

初始时，硬币序列为 $\{30,~25,~10,~35\}$。

第一回合，小 A 取走最右侧的硬币，序列变为 $\{30,~25,~10\}$，小 A 的累加价值为 $35$。

第二回合，小 B 取走最左侧的硬币，序列变为 $\{25,~10\}$，小 B 的累加价值为 $30$。

第三回合，小 A 取走最左侧的硬币，序列变为 $\{10\}$，小 A 的累加价值为 $35 + 25 = 60$。

第四回合，小 B 取走最左侧的硬币，序列变为空，小 B 的累加价值为 $30 + 10 = 40$，游戏结束。

小 A 获得的最大累计价值为 $60$。

数据范围与约定

对于全部的测试点，$1 \leq n \leq 5 \times 10^3$，$1 \leq c_i \leq 5 \times 10^3$。

提示：请注意，本题的空间限制为 $64$ Mib。