描述

N张纸牌被摆为一排，甲先从左端或右端取走一张纸牌，再由乙从左端或右端取走一张纸牌，再由甲从左端或右端取走一张纸牌……轮流抓下去，可以把所有纸牌抓完。
根据规则，抓的点数多者为胜，若甲、乙都是极聪明的人（ 各自都站在自己的立场 ），求甲至少得到多少点数。

格式

输入格式

第1行共输入1个正整数n(1<=n<=10000);
第2行共输入n个整数(每个整数都>0且<=10000)，分别代表第1张，第2张......第n张纸牌的点数。

输出格式

输出只包括一个整数k（0<k<=50000000），表示甲至少得到的点数。

样例1

样例输入1

2
3 6

样例输出1

6

样例2

样例输入2

5
1 2 3 4 5

样例输出2

9

样例3

样例输入3

8
50 9 18 66 81 40 75 34

样例输出3

224

限制

3s

提示

甲、乙二人都有各自的立场的意思是二人都只让自己拿到尽可能多的点数，不考虑对方。
题目默认甲极其聪明，所以“至少”说的是在乙也极其聪明的前提下甲能得到的点数。
样例2:
甲的至少获得的点数:5+3+1=9
样例3:
甲的至少获得的点数:50+75+81+18=224

来源

感谢 LXL 提供。