该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个数列 $A_1,A_2,…,A_N$，有两人在这个数列上进行游戏，交替取走数字。先手先行动，每人每次行动时只能取走一个数，也必须取走一个数，这个数必须是当时数列的首项或末项。

所有数字都被取完时，游戏结束。

游戏目的是看谁拿走的数字之和最大。两人都是非常聪明的，他们都会采用最佳的策略让自己取到的数字之和尽量大。请计算先手获得的数字之和。

输入格式

第一行：单个整数表示 $N$ 第二行：$N$ 个整数表示 $A_1,A_2,…,A_N$

输出格式

单个整数：表示先手取走的数字之和。

5
10 20 30 40 50

90

4
10 1000 100 1

1001

数据规模与约定

对于$30$%数据，$1≤n≤20$

对于$60$%数据，$1≤n≤300$

对于$100$%数据，$1≤n≤5000, 0≤a_i≤40000$