题目描述
马斯卡彭小蛋糕太好吃了，所以贪吃的 zyfgg 和 zcygg 在实验室偷吃马斯卡彭蛋糕，但是因为害怕不给 hzcgg 留点儿会让他生气，所以他们决定留下一个蛋糕。
zyfgg 认为留下最大的马斯卡彭蛋糕可以让 hzcgg 更开心，所以他每次会吃掉相邻两个马斯卡彭蛋糕中更小的一个；而 zcygg 认为留一个就算留，所以他每次会吃掉相邻两个马斯卡彭蛋糕中更大的一个。
实验室里有 n 个马斯卡彭蛋糕，ai 代表第 i 个蛋糕的大小，zyfgg 希望最后最大化留下的蛋糕，而 zcygg 希望最后最小化留下的蛋糕。如果双方都完全按照自己的想法轮流吃蛋糕，zyfgg 先吃，请你求出留给 hzcgg 的蛋糕的大小。
hzcgg正在吃马斯卡彭：
tle="" align="" />
zyfgg 认为留下最大的马斯卡彭蛋糕可以让 hzcgg 更开心，所以他每次会吃掉相邻两个马斯卡彭蛋糕中更小的一个；而 zcygg 认为留一个就算留，所以他每次会吃掉相邻两个马斯卡彭蛋糕中更大的一个。
实验室里有 n 个马斯卡彭蛋糕，ai 代表第 i 个蛋糕的大小，zyfgg 希望最后最大化留下的蛋糕，而 zcygg 希望最后最小化留下的蛋糕。如果双方都完全按照自己的想法轮流吃蛋糕，zyfgg 先吃，请你求出留给 hzcgg 的蛋糕的大小。
hzcgg正在吃马斯卡彭：
tle="" align="" />
输入
每个测试包含多个测试用例。 第一行包含测试用例数 t（1 ≤ t ≤ 105）。 测试用例说明如下。
每个测试用例的第一行包含一个整数 n（2 ≤ n ≤ 105）,代表马斯卡彭蛋糕数量。
每个测试用例的第二行包含 n 个整数 a1,a2,...,an（1 ≤ ai ≤105），代表蛋糕大小。
保证所有测试用例中 n 的总和不超过 105。
每个测试用例的第一行包含一个整数 n（2 ≤ n ≤ 105）,代表马斯卡彭蛋糕数量。
每个测试用例的第二行包含 n 个整数 a1,a2,...,an（1 ≤ ai ≤105），代表蛋糕大小。
保证所有测试用例中 n 的总和不超过 105。
输出
对于每个测试用例，输出一个整数，代表剩下的马斯卡彭蛋糕的大小。
样例输入
Copy
5
2
1 2
3
1 1 2
3
1 2 3
5
3 1 2 2 3
10
10 2 5 2 7 9 2 5 10 7
样例输出 Copy
2
1
2
2
7
来源/分类