题目描述
duxing哥遇到一个对手，两人决定一决高下。他们准备了一个有n个物品，排成一行，第i个物品价值为ai,两人轮流操作，每次操作取走任意一个还没被取走的物品，最后取得的物品价值和更高的人获胜。duxing哥很卑鄙，他事先对对方释放了降智打击，使得对方只会取走剩余物品中最左端没被选取的物品。duxing哥觉得自己优势很大，所以他决定让对方先取，同时决定让你来代替他来进行操作。你要输出duxing哥能取到的最大价值。
输入
第一行一个n，代表物品个数(1<=n<=1000000)
第二行n个数字，第i个数字ai代表第i个物品的价值(1<=ai<=1000000000)
输出
一个数字，代表duxing哥能取到的最大价值
样例输入
【样例输入1】
5
1 1 5 1 5
【样例输入2】
5
5 4 3 2 1
【样例输入3】
6
6 5 4 3 9 9
样例输出
【样例输出1】
10
【样例输出2】
6
【样例输出3】
23
来源/分类
浙江理工大学月赛