丢丢陈和陈丢丢在玩♂木棒游戏，一共有 nnn 个木棒，每根木棒都有自己的长度。
游戏的每次操作必须把最左边的连续 m(2≤m≤n)m(2\leq m\leq n)m(2≤m≤n) 根木棒合并为一根长度为原 mmm 根木棒长度之和的木棒后将新生成的木棒放在最左侧(原来的 mmm 根木棒消失)，同时操作者将得到与这根新生成木棒长度相同的分值。
丢丢陈和陈丢丢轮流进行操作，当只剩一根木棒时游戏结束。假设丢丢陈先手，并且他们采用了最优方案操作(使得分数之差最大的方案)，那么丢丢陈的分数减去陈丢丢的分数的最大值是多少呢？
丢丢陈和陈丢丢觉得普通的木棒在侮辱他们的智商，所以决定在游戏中添加了一些长度为非正数的虚拟木棒，混在普通木棒中，游戏规则不变。
测试数据有不超过 151515 组，用 EOF 标志表示输入结束，对于每一组数据满足：
第一行为一个整数 n(2≤n≤2×105)n(2\leq n\leq 2\times 10^5)n(2≤n≤2×105)，为木棒的个数。
第二行为 nnn 个整数 a1,a2,⋯ ,an(−5×104≤ai≤5×104)a_1,a_2,\cdots,a_n(-5\times 10^4\leq a_i\leq 5\times 10^4)a1,a2,⋯,an(−5×104≤ai≤5×104) 为 nnn 个木棒的长度。
对于每一组数据，输出一行共一个整数表示丢丢陈的分数减去陈丢丢的分数的最大值。
3 2 4 8 4 1 -7 -2 3
14 -3
