题目描述

小明和大强发现了一行 $N$ 个蛋糕，大小依次为 $a_1,a_2,\cdots,a_N$。

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

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

当只剩下一个蛋糕时，小明吃掉它，而大强吃掉他藏起来的所有蛋糕。如果两位小伙都采取最优策略以最大化他们吃到的蛋糕量，并且小明先进行回合，那么他们分别会吃到多少蛋糕？

输入格式

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

每个测试用例的格式如下：

第一行包含 $N$。下一行包含 $N$ 个空格分隔的整数 $a_1,a_2,\cdots,a_N$。

输出格式

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

样例

2
4
40 30 20 10
4
10 20 30 40

60 40
60 40

样例解释

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

小明将堆叠中间两个蛋糕。现在蛋糕的大小为 $[40,50,10]$。

大强将吃掉最左边的蛋糕。现在剩余的蛋糕的大小为 $[50,10]$。

小明堆叠剩余的两个蛋糕。

小明将吃到 $30+20+10=60$ 的蛋糕，而大强将吃到 $40$ 的蛋糕。

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

数据范围

对于 $100\%$ 的数据，$1\le T \le 10, 2\le N \le 5 \times 10^5, 1\le a_i \le 10^9$，且 $N$ 为偶数。

• 测试点 1：所有 $a_i$ 相等。
• 测试点 2：$N \le 10$。
• 测试点 3-6：$N \le 5000$。
• 测试点 7-10：没有额外限制。