题目描述

给定一个长度为 $N$ 的正整数数组 $a_1, a_2, \dots, a_N$。保证 $N$ 是一个偶数。

Alice 和 Bob 正在用这个数组玩一个游戏。游戏在两人之间轮流进行，由 Alice 先手。每个回合中，玩家执行以下操作之一：

• Alice 的回合：选择两个相邻的元素并将它们合并。合并后的新元素的值为这两个元素的值之和。操作后，数组的长度将减 $1$。
• Bob 的回合：选择数组最左边或最右边的元素并将其拿走。拿走的元素将不再属于该数组。操作后，数组的长度将减 $1$。

当数组中只剩下唯一一个元素时，游戏结束。此时，Alice 将获得这个剩余的元素，而 Bob 将获得他之前拿走的所有元素。

游戏的目标是：两位玩家都希望自己最终获得的总价值（元素值之和）尽可能大。在双方均采取最优策略的情况下，请分别计算出 Alice 和 Bob 最终获得的总价值。

输入格式

第一行包含一个整数 $T$ —— 表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个正整数 $N$ —— 数组的长度，保证 $N$ 为偶数。
• 第二行包含 $N$ 个空格分隔的整数 $a_1, a_2, \dots, a_N$ —— 表示数组的元素。

输出格式

对于每个测试用例，输出一行两个整数 $A$ 和 $B$ —— 分别表示在双方均采取最优策略的情况下，Alice 和 Bob 最终获得的总价值。两个整数之间用一个空格隔开。

样例输入 1

2
4
40 30 20 10
4
10 20 30 40

样例输出 1

60 40
60 40

说明

样例解释

在第一个测试用例中，双方的最优策略如下：

• 回合 1（Alice）：将中间的两个元素合并。数组变为 $[40, 50, 10]$。
• 回合 2（Bob）：拿走最左边的元素 $40$。数组变为 $[50, 10]$。
• 回合 3（Alice）：合并剩下的两个元素。数组变为 $[60]$。 游戏结束。Alice 获得的元素为 $60$（相当于初始的 $30 + 20 + 10$），Bob 拿走的元素为 $40$。

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

数据范围

• 对于所有测试点，保证 $1 \le T \le 10$。
• 对于每个测试用例，保证 $2 \le N \le 5 \times 10^5$，且 $N$ 为偶数。
• 对于每个测试用例，保证 $1 \le a_i \le 10^9$。
• 保证同一测试点内所有测试用例的 $N$ 之和不超过 $10^6$。
• 保证所有的输入数值均为整数。