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

题目描述

小林最近迷上了博弈问题，他拉着小伊一起来玩游戏分糖果，具体的，现在有 n 包糖果，从左到右依次排成一行，第 i 包糖果中有 $a_i$ 个糖果，小林和小伊从左到右对 n 包糖果进行分配，分配权一开始在小林手里，小林可以将 n 包糖果中最左端的糖果分配给自己或者小伊，本次分配中没有拿到糖果的人将拥有下一次的分配权，小林和小伊都足够聪明，会采用最优的策略进行分配，保证自己最后拥有的糖果总数最多，如此分配 n 轮后，问小林和小伊中糖果更多的那个人所拥有的糖果数量。

输入格式

第一行包含一个整数 n，表示一共有 n 包糖果。

第二行包含 n 个整数，第 i 个数 $a_i$ 表示第 i 包糖果中的糖果数量。

输出格式

输出一个整数，表示小林和小伊中任一人可以获得的最大收益。

5
1 3 5 7 9

13

样例解释

轮 1：

小林选择把 1 分给 小伊 小林：0

• 小伊：1
• 剩余：[3, 5, 7, 9]
• 当前分配权：小林（因为没拿糖）

轮 2：

小林选择把 3 分给 小伊

• 小林：0
• 小伊：1 + 3 = 4
• 剩余：[5, 7, 9]
• 当前分配权：小林

轮 3：

小林选择把 5 分给 自己

• 小林：5
• 小伊：4
• 剩余：[7, 9]
• 当前分配权：小伊（因为小林拿了糖）

轮 4：

小伊分配 7，她可以：

• 给小林
• 给自己

她选择把 7 给小林

• 小林：5 + 7 = 12
• 小伊：4
• 剩余：[9]
• 当前分配权：小伊

轮 5：

小伊把 9 分给自己

• 小林：12
• 小伊：4 + 9 = 13

最终：

• 小林：12
• 小伊：13

最大收益是：13

样例2

数据范围与约定

对于 40% 的数据，$1 ≤ n ≤ 20。$

对于 100% 的数据，$1 ≤ n, a_i ≤ 100000。$