题目描述

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

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

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

输入格式

第一行输入一个整数 $n$。

接下来 $n$ 行，第 $i+1$ 行有一个整数 $c_i$。

输出格式

输出一个整数，表示贝西可以获得的最大价值。

样例输入

4
30
25
10
35

样例输出

60

样例说明

贝西最好的取法是先取 35，然后邦妮会取 30，贝西再取 25，邦妮最后取 10。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le5\times10^3$，$1\le c_i\le5\times10^3$。