题目描述

小 A 和小 B 在玩游戏。

初始时，给出一个含 $n$ 个数 $c_i$ 的序列。

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

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

输入格式

输入的第一行是一个整数 $n \ (1 \leq n \leq 5 \times 10^3)$。

下来 $n$ 个数 $c_i \ (1 \leq c_i \leq 5 \times 10^3)$。

输出格式

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

输入输出样例 #1

输入 #1

4 
30 25 10 35

输出 #1

60

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