题目描述

贝西和邦妮找到了一个藏宝箱，里面都是金币！但是身为两头牛，她们不能到商店里把金币换成好吃的东西，于是她们只能用这些金币来玩游戏了。

藏宝箱里一共有$\red{N}$枚金币，第$\red{i}$枚金币的价值是$\red{Ci}$。贝西和邦妮把金币排成一条直线，她们轮流取金币，看谁取到的钱最多。贝西先取，每次只能取一枚 金币，而且只能选择取直线两头的金币，不能取走中间的金币。当所有金币取完之后，游戏就结束了。

贝西和邦妮都是非常聪明的，她们会采用最好的办法让自己取到的金币最多。请帮助贝西计算一下，她能拿到多少钱？

输入格式

第一行：单个整数$\red{N，}$表示硬币的数量，$\red{1<=N≤}$$\red{5000}$

第二行到第$\red{N+1}$行：第$\red{i+l}$行有一个整数$\red{Ci，}$代表第$\red{i}$块硬币的价值，$\red{1≤}$$\red{Ci≤}$$\red{5000}$

输出格式

第一行：单个整数，表示如果双方都按最优策略玩游戏，先手可以拿到的最大价值

样例

输入样例

4
30
25
10
35

输出样例

60

提示

贝西最好的取法是先取$\red{35，}$然后邦妮会取$\red{30，}$贝西再取$\red{25，}$邦妮最后取$\red{10}$