题目描述

给定一个数列 $a_1,a_2,\dots,a_n$，小爱与小艾交替取走一个数字，小爱先取。两人取数时，都只能挑选当时数列的首项或末项。取数是必须要完成的动作，不能不取，直到所有的数字都被取走为止。

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

输入格式

• 单个整数表示 $n$
• $n$ 个整数表示 $a_1,a_2,\dots,a_n$

输出格式

• 单个整数：表示先手小爱取走的最大数字之和。

5
10 20 30 40 50

90

数据范围

• $30\%$，$1\leq n\leq 20$
• $60\%$，$1\leq n\leq 300$
• $100\%$，$1\leq n\leq 5000$
• $0\leq a_i\leq 40000$