给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。 Alice 和 Bob 将用这个数组玩一个游戏。他们将交替轮流,爱丽丝先走。
每回合,玩家必须选择在 $$$a$$$ 中至少出现一次的值 $$$x \gt 0$$$。然后,
- 玩家为数组中的每个值 $$$x$$$ 赚取 $$$1$$$ 点,
- 数组中的每个值 $$$x$$$ 减少 $$$1$$$ 并变为 $$$x-1$$$。
当没有$$$x$$$可供选择时游戏结束;也就是说,当数组中的所有元素都为零时。
鉴于两名玩家都希望最大化自己的分数并以最佳方式进行比赛,请计算每个玩家最终获得的分数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^{5}$$$) — 数组的大小。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{9}$$$) — 数组的元素。
保证所有测试用例的$$$n$$$总和不超过$$$2\cdot 10^{5}$$$。
输出
对于每个测试用例,输出两个整数,即 Alice 和 Bob 在双方都表现最佳的情况下将获得的分数。
示例
输入复制
332 1 153 3 3 5 549 9 9 9
输出复制
3 110 920 16
注意
展示台链接
在第一个测试用例中,Alice 在第一步中选择 $$$x=1$$$。该数组变为 $$$[2,0,0]$$$,她获得 $$$2$$$ 积分。之后,Bob 被迫选择 $$$x=2$$$。该数组变为 $$$[1,0,0]$$$,Bob 获得 $$$1$$$ 点。最后,Alice 被迫选择 $$$x=1$$$ 并多赚一分。之后数组就是$$$[0,0,0]$$$,所以游戏结束。总共,Alice 获得了 $$$3$$$ 分,Bob 获得了 $$$1$$$ 分。
在第三个测试用例中,每个玩家将减少所有元素并每次移动赚取 $$$4$$$ 点。 Alice 将获得 $$$5 \cdot 4 = 20$$$ 积分,而 Bob 将仅获得 $$$4\cdot 4 = 16$$$ 积分。