题目描述

​ 很多天以后，xjc终于集齐了七颗龙珠，召唤出了神龙，并郑重的许下了愿望：“希望疫情消失”，然而神龙表示这个归gov管，让xjc换一个愿望，于是xjc重新许下一个愿望：给他一个可以玩一个月都不无聊的游戏。

​ 于是神龙赐给了xjc这样一个双人对抗游戏。

​ $n$颗龙珠排成一排，每颗龙珠的价值是$v_i$，xjc每次可以从最左边/最右边拿走其中一颗，然后神龙会在剩下的龙珠中，挑选一颗拿走。一人一龙重复这样的过程，直到一颗龙珠都没有为止。

​ 因为龙珠很值钱，所以神龙给了xjc这样一个要求：

​ 神龙会以让xjc拿走的龙珠价值之和最小为目标，所以每次决策都是为了达成这个全局目标的。

​ 如果xjc在这样的前提条件下，拿走的龙珠价值之和是他理论上能拿走的最大值，那么神龙就会把这些龙珠送给他，否则游戏重来。

​ xjc玩了两整天，然而一次都没赢，他很恼火，就把每一把的初始情况告诉了你，请你帮他算一下，他到底最多能拿多少？

输入格式

​ 第一行输入一个整数$n$，表示龙珠个数，保证$n$是偶数。

​ 接下来一行，一共$n$个数字$v_i$，表示从左到右每一颗龙珠的价值。

输出格式

一共一个数字，表示xjc最多能拿走多少。

样例输入1

4
2 9 7 3

样例输出1

10

样例解释1

显然xjc无论拿左边还是右边，神龙都会拿走第二颗9，xjc都只能拿到7，所以xjc还不如一开始拿右边的3，再拿右边的7。

样例输入2

10
1 2 3 4 5 6 7 8 9 10

样例输出2

30

样例解释2

一人一龙的最优决策都是每次拿掉最右边的，所以xjc拿到了10,8,6,4,2，一共是30。

数据规模与约定

对于$10\%$的数据：$n= 6$。

对于$30\%$的数据：$n\leq 20$。

对于$80\%$的数据：$n\leq 300$。

对于$100\%$的数据：$n\leq500,1\leq v_i\leq 10^9$。