题目描述

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 在两头奶牛都采取最优策略的情况下分别吃到的蛋糕量。

2
4
40 30 20 10
4
10 20 30 40

60 40
60 40

提示

样例解释

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

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：没有额外限制。