seuOJ110 - 木棒♂游戏

丢丢陈和陈丢丢在玩♂木棒游戏，一共有 $n$ 个木棒，每根木棒都有自己的长度。

游戏的每次操作必须把最左边的连续 $m(2\leq m\leq n)$ 根木棒合并为一根长度为原 $m$ 根木棒长度之和的木棒后将新生成的木棒放在最左侧(原来的 $m$ 根木棒消失)，同时操作者将得到与这根新生成木棒长度相同的分值。

丢丢陈和陈丢丢轮流进行操作，当只剩一根木棒时游戏结束。假设丢丢陈先手，并且他们采用了最优方案操作(使得分数之差最大的方案)，那么丢丢陈的分数减去陈丢丢的分数的最大值是多少呢？

丢丢陈和陈丢丢觉得普通的木棒在侮辱他们的智商，所以决定在游戏中添加了一些长度为非正数的虚拟木棒，混在普通木棒中，游戏规则不变。

测试数据有不超过 $15$ 组，用 EOF 标志表示输入结束，对于每一组数据满足：

第一行为一个整数 $n(2\leq n\leq 2\times 10^5)$ ，为木棒的个数。

第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n(-5\times 10^4\leq a_i\leq 5\times 10^4)$ 为 $n$ 个木棒的长度。

对于每一组数据，输出一行共一个整数表示丢丢陈的分数减去陈丢丢的分数的最大值。

14
-3