B. 乌龟与小猪的游戏 2

• 时间限制：$1$ 秒
• 内存限制：$256$ 兆字节

乌龟和小猪正在一个序列上玩游戏。他们得到一个序列 $a_1, a_2, \dots, a_n$，乌龟先手。乌龟和小猪轮流进行回合（因此，乌龟执行第 $1$ 回合，小猪执行第 $2$ 回合，乌龟执行第 $3$ 回合，以此类推）。

游戏流程如下：

• 设当前序列的长度为 $m$。如果 $m = 1$，游戏结束。
• 如果游戏尚未结束且轮到乌龟的回合，乌龟必须选择一个整数 $i$，满足 $1 \le i \le m-1$，将 $a_i$ 设为 $\max(a_i, a_{i+1})$，并删除 $a_{i+1}$。
• 如果游戏尚未结束且轮到小猪的回合，小猪必须选择一个整数 $i$，满足 $1 \le i \le m-1$，将 $a_i$ 设为 $\min(a_i, a_{i+1})$，并删除 $a_{i+1}$。

乌龟希望最终得到的 $a_1$ 值尽可能大，而小猪希望最终得到的 $a_1$ 值尽可能小。如果双方都采取最优策略，求最终 $a_1$ 的值。

可以参阅注释以进一步理解题意。

输入

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。

每个测试用例的描述如下：

• 第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— 序列的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^5$）—— 序列 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出

对于每个测试用例，输出一个整数 —— 双方都采取最优策略时，最终 $a_1$ 的值。

样例

输入

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

输出

2
1
2
2
7

注释

• 第一个测试用例：初始序列为 $[1, 2]$。乌龟只能选择 $i = 1$。然后他将 $a_1$ 设为 $\max(a_1, a_2) = 2$，并删除 $a_2$。序列变为 $[2]$。接着序列长度变为 $1$，游戏结束。最终 $a_1$ 的值为 $2$，因此输出 $2$。

• 第二个测试用例：一种可能的游戏过程如下： 初始序列 $[1, 1, 2]$。 乌龟选择 $i = 2$。他将 $a_2$ 设为 $\max(a_2, a_3) = 2$，并删除 $a_3$。序列变为 $[1, 2]$。 小猪选择 $i = 1$。他将 $a_1$ 设为 $\min(a_1, a_2) = 1$，并删除 $a_2$。序列变为 $[1]$。 序列长度变为 $1$，游戏结束。最终 $a_1$ 的值为 $1$。

• 第四个测试用例：一种可能的游戏过程如下： 初始序列 $[3, 1, 2, 2, 3]$。 乌龟选择 $i = 4$。他将 $a_4$ 设为 $\max(a_4, a_5) = 3$，并删除 $a_5$。序列变为 $[3, 1, 2, 3]$。 小猪选择 $i = 3$。他将 $a_3$ 设为 $\min(a_3, a_4) = 2$，并删除 $a_4$。序列变为 $[3, 1, 2]$。 乌龟选择 $i = 2$。他将 $a_2$ 设为 $\max(a_2, a_3) = 2$，并删除 $a_3$。序列变为 $[3, 2]$。 小猪选择 $i = 1$。他将 $a_1$ 设为 $\min(a_1, a_2) = 2$，并删除 $a_2$。序列变为 $[2]$。 序列长度变为 $1$，游戏结束。最终 $a_1$ 的值为 $2$。