Problem 1. Cake Game

USACO 2024 December Contest, Silver

Bessie 和 Elsie 发现了一行 $N$ 个蛋糕（$2 \leq N \leq 5\cdot 10^5$，$N$ 为偶数），大小依次为 $a_1,a_2,\dots,a_N$（$1\le a_i\le 10^9$）。

两头奶牛都想吃到尽可能多的蛋糕。但是，作为非常文明的奶牛，她们决定玩一个游戏来分割蛋糕！游戏在两头奶牛之间轮流进行回合。每个回合进行以下两者之一：

1. Bessie 选择两个相邻的蛋糕并将它们堆叠起来，制造大小为两者大小之和的一个新蛋糕。
2. Elsie 选择最左边或最右边的蛋糕藏起来。

当只剩下一个蛋糕时，Bessie 吃掉它，而 Elsie 吃掉她藏起来的所有蛋糕。如果两头奶牛都采取最优策略以最大化她们吃到的蛋糕量，并且 Bessie 先进行回合，那么每头奶牛将会吃到多少蛋糕？

输入格式（从终端 / 标准输入读入）：

每个测试点包含 $T$（$1\le T\le 10$）个独立的测试用例。输入保证一个测试点中的所有 $N$ 之和不超过 $10^6$。

每个测试用例的格式如下。第一行包含 $N$。下一行包含 $N$ 个空格分隔的整数 $a_1,a_2,\ldots,a_N$。

输出格式（输出至终端 / 标准输出）：

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

输入样例：

2
4
40 30 20 10
4
10 20 30 40

输出样例：

60 40
60 40

对于第一个测试用例，在最优策略下，

1. Bessie 将堆叠中间两个蛋糕。现在蛋糕的大小为 $[40,50,10]$。
2. Elsie 将吃掉最左边的蛋糕。现在剩余的蛋糕的大小为 $[50,10]$。
3. Bessie 堆叠剩余的两个蛋糕。

Bessie 将吃到 $30+20+10=60$ 的蛋糕，而 Elsie 将吃到 $40$ 的蛋糕。

第二个测试用例是第一个测试用例反转的情况，因此答案相同。

测试点性质： 测试点 2：所有 $a_i$ 相等。测试点 3：$N\le 10$。测试点 4-7：$N\le 5000$。测试点 8-11：没有额外限制。

供题：Linda Zhao，Agastya Goel，Gavin Ye