金币游戏
说明
贝西和她的朋友邦妮挖到了一个宝箱，里面藏着 $N$ 枚金币！但金币对奶牛没用，她们一直用这些金币玩游戏。游戏的目的是看谁拿走的金币最值钱。游戏开始之前，金币被排成一列，在第 $i$ 个位置的金币面值为 $C_i$ 。贝西和邦妮轮流取金币，每次她们只能从队头或队尾的两块金币中挑一块拿走，不能一块也不拿。所有金币取完之后，游戏就结束了。贝西和邦妮都是非常聪明的，会采用最好的策略让自己取到的金币面值之和最大。假设贝西是先手，请帮她计算一下，她最多能拿走多少钱的金币？
输入格式
第一行：单个整数 $N, 1 \leq N \leq 5000$
第二行到第 $N + 1$ 行：第 $i + 1$ 行有一个整数：$C_i, 1 \leq C_i \leq 5000$
输出格式
单个整数：先手可以拿到的最大面值之和
样例
4
30
25
10
3560