题目背景

小林最近迷上了博弈问题。

题目描述

有 $n$ 包糖果从左到右依次排成一行，第 $i$ 包糖果中有 $a_i$ 个糖果。小林和小伊从左到右对 $n$ 包糖果进行分配，分配权一开始在小林手里，小林可以将 $n$ 包糖果中最左端的糖果分配给自己或者小伊，本次分配中没有拿到糖果的人将拥有下一次的分配权。

如果小林和小伊都足够聪明，会采用最优的策略进行分配，保证自己最后拥有的糖果总数最多，如此分配 $n$ 轮后，求出小林和小伊中糖果更多的那个人所拥有的糖果数量。

输入格式

输入共 $2$ 行。

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

输出格式

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

5
1 3 5 7 9

13

提示

样例解释：如下是他们的游戏过程。

• 小林将 $1$ 分给自己；此时小林和小伊的糖果数分别为 $1,0$；
• 小伊将 $3$ 分给小林；此时小林和小伊的糖果数分别为 $4,0$；
• 小伊将 $5$ 分给自己；此时小林和小伊的糖果数分别为 $4,5$；
• 小林将 $7$ 分给小伊；此时小林和小伊的糖果数分别为 $4,12$；
• 小林将 $9$ 分给自己；此时小林和小伊的糖果数分别为 $13,12$。

可以证明这是最优的游戏策略。

本题采用捆绑测试。

• Subtask 1（40pts）：保证 $n\le 20$；
• Subtask 2（60pts）：无额外约束。

对于 $100\%$ 的数据，保证 $1\le n,a_i\le 10^5$。