CF2003B.Turtle and Piggy Are Playing a Game 2

Turtle 和 Piggy 正在玩一个关于序列的游戏。他们得到一个序列 $a_1, a_2, \ldots, a_n$，Turtle 先手。Turtle 和 Piggy 轮流操作（即 Turtle 先操作，Piggy 第二次操作，Turtle 第三次操作，以此类推）。

游戏规则如下：

• 设当前序列长度为 $m$。如果 $m = 1$，则游戏结束。
• 如果游戏未结束且轮到 Turtle 操作，则 Turtle 必须选择一个整数 $i$，满足 $1 \le i \le m - 1$，将 $a_i$ 赋值为 $\max(a_i, a_{i + 1})$，并移除 $a_{i + 1}$。
• 如果游戏未结束且轮到 Piggy 操作，则 Piggy 必须选择一个整数 $i$，满足 $1 \le i \le m - 1$，将 $a_i$ 赋值为 $\min(a_i, a_{i + 1})$，并移除 $a_{i + 1}$。

Turtle 希望最终 $a_1$ 的值最大，而 Piggy 希望最终 $a_1$ 的值最小。如果双方都采取最优策略，求最后 $a_1$ 的值。

你可以参考提示部分获得进一步的说明。

每个测试点包含多组测试数据。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来是每组测试数据的描述。

每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^5$），表示序列 $a$ 的元素。

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

对于每组测试数据，输出一个整数，表示在双方都采取最优策略的情况下，最终 $a_1$ 的值。

在第一个测试用例中，初始 $a = [1, 2]$。Turtle 只能选择 $i = 1$，然后他会将 $a_1$ 赋值为 $\max(a_1, a_2) = 2$ 并移除 $a_2$。此时序列 $a$ 变为 $[2]$。序列长度变为 $1$，游戏结束。$a_1$ 的值为 $2$，因此你应输出 $2$。

在第二个测试用例中，可能的游戏过程如下：

• 初始 $a = [1, 1, 2]$。
• Turtle 可以选择 $i = 2$，然后他会将 $a_2$ 赋值为 $\max(a_2, a_3) = 2$ 并移除 $a_3$。此时序列 $a$ 变为 $[1, 2]$。
• Piggy 可以选择 $i = 1$，然后他会将 $a_1$ 赋值为 $\min(a_1, a_2) = 1$ 并移除 $a_2$。此时序列 $a$ 变为 $[1]$。
• 序列长度变为 $1$，游戏结束。最终 $a_1$ 的值为 $1$。

在第四个测试用例中，可能的游戏过程如下：

• 初始 $a = [3, 1, 2, 2, 3]$。
• Turtle 可以选择 $i = 4$，然后他会将 $a_4$ 赋值为 $\max(a_4, a_5) = 3$ 并移除 $a_5$。此时序列 $a$ 变为 $[3, 1, 2, 3]$。
• Piggy 可以选择 $i = 3$，然后他会将 $a_3$ 赋值为 $\min(a_3, a_4) = 2$ 并移除 $a_4$。此时序列 $a$ 变为 $[3, 1, 2]$。
• Turtle 可以选择 $i = 2$，然后他会将 $a_2$ 赋值为 $\max(a_2, a_3) = 2$ 并移除 $a_3$。此时序列 $a$ 变为 $[3, 2]$。
• Piggy 可以选择 $i = 1$，然后他会将 $a_1$ 赋值为 $\min(a_1, a_2) = 2$ 并移除 $a_2$。此时序列 $a$ 变为 $[2]$。
• 序列长度变为 $1$，游戏结束。最终 $a_1$ 的值为 $2$。

由 ChatGPT 4.1 翻译