CF 2003B Turtle and Piggy Are Playing a Game 2

Turtle 和 Piggy 正在玩一个序列游戏。他们得到一个序列 a1、a2、…、an，Turtle 先走。Turtle 和 Piggy 轮流走（因此，Turtle 先走第一圈，Piggy 再走第二圈，Turtle 再走第三圈，等等）。

游戏进行如下：

让序列的当前长度为 m。如果 m=1，游戏结束。

如果游戏没有结束并且轮到 Turtle，那么 Turtle 必须选择一个整数 i，使得 1≤i≤m−1，将 ai 设置为 max(ai,ai+1)，并移除 ai+1。

如果游戏没有结束并且轮到 Piggy，那么 Piggy 必须选择一个整数 i，使得 1≤i≤m−1，将 ai 设置为 min(ai,ai+1)，并移除 ai+1。

Turtle 希望最终最大化 a1 的值，而 Piggy 希望最终最小化 a1 的值。如果双方都发挥最佳，则求出最后 a1 的值。

您可以参考注释以获得进一步说明。

输入

每个测试包含多个测试用例。第一行包含测试用例数 t（1≤t≤104）。测试用例的描述如下。

每个测试用例的第一行包含一个整数 n

（2≤n≤105）——序列的长度。

每个测试用例的第二行包含 n 个整数 a1、a2、…、an（1≤ai≤105）——序列 a 的元素。

保证所有测试用例的 n 之和不超过 105。

输出

对于每个测试用例，输出一个整数——如果双方都发挥最佳，则最后 a1 的值。

----

-----------

第一个人会优先删除一个最小值，第二个人会优先删除一个最大值，那么剩下的就是就只中间值了。

排序，输出中间值，然后就是如果n为奇数，输出的正好是正中间的值，如果n为偶数，输出的是后面的那个是，因为第一个人会优先删除那个较小值。