题目描述

Alice 和 Bob 正在玩取数游戏。

序列 A 包含 $N$ 个整数，从左到右排成一行，依次是 $A_1, A_2, ……, A_N$.

两个人轮流从两端取数，不能从中间取。每人每次只能取走一个，Alice 先取。当所有数都被取完后，谁取到的数的和大，谁就获胜。

两个人都足够聪明，都想获得最后的胜利。

问：Alice 取到的数之和最大是多少？

输入格式

第一行：一个整数 $N$

接下来 $N$ 行：每行一个整数，依次表示 $A_1, A_2, ……, A_N$

输出格式

一个整数，表示 Alice 能取到的数的和的最大值

样例输入

4
1
2
5
3

样例输出

6

数据范围

100% 的数据：$1 ≤ N, A_i ≤ 5000$