Azizkhan 和 Temirulan 非常喜欢瑞士巧克力。最近他们买了一块由 $n$ 块巧克力组成的巧克力棒。每一块都有一定的甜度。此外，某一块的甜度可能是负数。

为了公平地分配巧克力棒，他们制定了一些吃巧克力的规则：

• 巧克力块从左到右编号为 $1, 2, \dots, n$。
• Azizkhan 从左侧开始吃，Temirulan 从右侧开始吃。
• Azizkhan 和 Temirulan 轮流吃巧克力。
• 每位玩家在自己的回合中可以吃掉一块或多块巧克力。
• Azizkhan 先手，第一回合可以吃掉 1 块或 2 块。
• 如果上一回合吃掉了 $k$ 块，那么当前玩家必须吃掉 $k$ 块或 $k+1$ 块。
• 如果无法进行下一步操作，他们就停止吃巧克力。

Azizkhan 和 Temirulan 都是好胜的人。他们每个人都希望自己吃到的甜度总和比对方多。换句话说，每位玩家都试图最大化自己吃到的甜度总和与对方吃到的甜度总和之差。请帮助他们计算，如果两位玩家都是超级无敌聪明且最优的，那么 Azizkhan 吃到的甜度总和与 Temirulan 吃到的甜度总和之差是多少。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 4000$)：巧克力棒中巧克力的块数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^4 \le a_i \le 10^4$)：每一块巧克力的甜度值。

输出格式

输出一行，包含一个整数：如果双方都采取最优策略，Azizkhan 吃到的甜度总和与 Temirulan 吃到的甜度总和之差。

样例

样例输入 1

5
1 2 3 4 5

样例输出 1

-3

样例输入 2

6
-2 5 100 6 3 4

样例输出 2

90