P11452 [USACO24DEC] Cake Game S

Bessie 和 Elsie 发现了一行 $N$ 个蛋糕（$2≤N≤5⋅10^5$ ，$N$ 为偶数），大小依次为 $a_1,a_2,\cdots,a_N$（$1≤a_i≤10^9$）。 两头奶牛都想吃到尽可能多的蛋糕。但是，作为非常文明的奶牛，她们决定玩一个游戏来分割蛋糕！游戏在两头奶牛之间轮流进行回合。每个回合进行以下两者之一： 1. Bessie 选择两个相邻的蛋糕并将它们堆叠起来，制造大小为两者大小之和的一个新蛋糕。 2. Elsie 选择最左边或最右边的蛋糕藏起来。 当只剩下一个蛋糕时，Bessie 吃掉它，而 Elsie 吃掉她藏起来的所有蛋糕。如果两头奶牛都采取最优策略以最大化她们吃到的蛋糕量，并且 Bessie 先进行回合，那么每头奶牛将会吃到多少蛋糕？

每个测试点包含 $T$（$1≤T≤10$）个独立的测试用例。输入保证一个测试点中的所有 $N$ 之和不超过 $10^6$。 每个测试用例的格式如下。 第一行包含 $N$。下一行包含 $N$ 个空格分隔的整数 $a_1,a_2,\cdots,a_N$。

对于每个测试用例，输出一行，包含 $b$ 和 $e$，表示 Bessie 和 Elsie 在两头奶牛都采取最优策略的情况下分别吃到的蛋糕量。

### 样例解释 对于第一个测试用例，在最优策略下， Bessie 将堆叠中间两个蛋糕。现在蛋糕的大小为 $[40,50,10]$。 Elsie 将吃掉最左边的蛋糕。现在剩余的蛋糕的大小为 $[50,10]$。 Bessie 堆叠剩余的两个蛋糕。 Bessie 将吃到 $30+20+10=60$ 的蛋糕，而 Elsie 将吃到 $40$ 的蛋糕。 第二个测试用例是第一个测试用例反转的情况，因此答案相同。 ### 测试点性质 - 测试点 1：样例。 - 测试点 2：所有 $a_i$ 相等。 - 测试点 3：$N≤10$。 - 测试点 4-7：$N≤5000$。 - 测试点 8-11：没有额外限制。