吃糖果

你和Bob都很爱吃糖果，今天小V买回来n个糖果，排成一排，已知每一个糖果吃了后都会获得一个快乐值v1，v2，v3......vn。
现在你和Bob开始轮流选择糖果吃，每个人每次只能从糖果排的排首或者排尾来拿出一个糖果吃。石头剪刀布后决定你先手，你和Bob都希望获得尽量多的快乐值，因此你和Bob都采取最优策略来吃糖果。
聪明的你知道在你们都采取最优策略的情况下，你最多能获得多少快乐值吗？

题目包括多组数据。
每组数据第一行为n，表示有n个糖果。(1<=n<=1e3)
每组数据第二行有n个数字，第i个数字表示这n个糖果的快乐值vi。（1<=vi<=1e5）

每组数据输出一行，包含一个数字，表示都采取最优策略的情况下你先手能获得的最多的快乐值。
（注意，输出的行末没有空格。）

4
1 500 2020 90
3
1 100 1

2021
2

"文远知行杯"杭州电子科技大学第二十一届程序设计竞赛