B4168 [GXPC-S 2024] 分糖果

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

有 $n$ 包糖果从左到右依次排成一行，第 $i$ 包糖果中有 $a_i$ 个糖果。小林和小伊从左到右对 $n$ 包糖果进行分配，分配权一开始在小林手里，小林可以将 $n$ 包糖果中最左端的糖果分配给自己或者小伊，本次分配中**没有拿到糖果**的人将拥有下一次的分配权。 如果小林和小伊都足够聪明，会采用最优的策略进行分配，保证自己最后拥有的糖果总数最多，如此分配 $n$ 轮后，求出小林和小伊中**糖果更多的那个人**所拥有的糖果数量。

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

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

样例解释：如下是他们的游戏过程。 - 小林将 $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$。