别问为什么这么简单还要求助，因为我是蒟蒻

在遥远的魔法王国里，有一位年轻的魔法师——艾文，他最近发现了一串神秘的魔法宝石，每颗宝石都蕴含着不同的魔法能量。这些宝石按照某种顺序排列着，形成了一个数列 b 1 , b 2 , … , b n b 1 ​ ,b 2 ​ ,…,b n ​。

艾文的好友莉娜是一位同样出色的魔法师，她对这串宝石产生了浓厚的兴趣。两人决定玩一个游戏：轮流从数列中“吸取”宝石中的魔法能量。艾文先开始。每次“吸取”时，他们只能从数列的首颗或末颗宝石中选择一颗，并吸收其中的魔法能量。这个过程必须持续进行，直到所有的宝石都被“吸取”完毕。

游戏的目的是尽可能多地吸收魔法能量。艾文和莉娜都是非常聪明的魔法师，他们会用尽一切策略来确保自己吸收的魔法能量最多。现在，请你帮助艾文计算，他最多能吸收到多少魔法能量。

输入格式 第一行是一个整数 n，表示宝石的数量。 第二行是 n 个整数，表示每颗宝石蕴含的魔法能量值 b 1 ​ ,b 2 ​ ,…,b n ​ 。

输出格式: 输出一个整数，表示艾文最多能吸收到的魔法能量值。 样例数据

数据范围 对于 30 % 的数据， 1 ≤ � ≤ 20 1≤n≤20 对于 60 % 的数据， 1 ≤ � ≤ 300 1≤n≤300 对于 100 % 的数据， 1 ≤ � ≤ 5000 , 0 ≤ � � ≤ 40000 1≤n≤5000,0≤b i ​ ≤40000