题目描述

堆是一种特殊的基于树的数据结构。 在小顶堆中，对于任意节点R，如果R是C的父亲节点，则R的键值小于或等于C的键值。 一般地，我们可以在A1，A2，...，An数组中储存n大小的堆，其中Ai表示第i个节点的键值。 根节点是第1个节点，其中第i（2≤i≤n）个节点的父亲节点是第[i/2]个节点。

JS和Deartanker在小顶堆上玩游戏。两人轮流移动，JS先移动。在每次移动中，当前玩家选择一个没有子节点的节点，将其键值添加到该玩家的分数中，并从堆中移除该节点。

当堆为空时游戏结束，玩家们都希望自己的得分最大化。请写一个程序来计算游戏的最终结果。

输入格式

输入第一行包含一个整数T（1≤T≤10000），代表测试用例数量。 对于每个测试用例，第一行包含一个整数n（1≤n≤100000），代表节点数。 第二行有n个整数A1，A2，...，An（1≤Ai≤10^9，A[i/2]≤A[i]）。 保证sum(n)≤10^6。

输出格式

对于每个测试用例，打印一行两个整数J和D，代表JS和Deartanker的最终得分。

1
3
1 2 3

4 2