← 返回题目列表

Codeforces · 2003/B

B. 乌龟和小猪正在玩游戏2

中文机器翻译题面 查看原题

海龟和小猪正在按顺序玩游戏。给它们一个序列 $$$a_1, a_2, \ldots, a_n$$$,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}$$$。

海龟最终希望最大化 $$$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, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — 序列 $$$a$$$ 的元素。

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

输出

对于每个测试用例,输出一个整数 - 如果两个玩家都发挥最佳,则最终 $$$a_1$$$ 的值。

示例

输入 #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

输出 #1

2
1
2
2
7

注意

在第一个测试用例中,最初 $$$a = [1, 2]$$$。海龟只能选择$$$i = 1$$$。然后他会将 $$$a_1$$$ 设置为 $$$\max(a_1, a_2) = 2$$$ 并删除 $$$a_2$$$。序列 $$$a$$$ 变为 $$$[2]$$$。那么序列的长度就变成$$$1$$$,游戏结束。 $$$a_1$$$ 的值为 $$$2$$$,因此您应该输出 $$$2$$$。

在第二个测试用例中,可能的游戏流程之一如下:

- 最初 $$$a = [1, 1, 2]$$$。
- 海龟可以选择 $$$i = 2$$$。然后他会将 $$$a_2$$$ 设置为 $$$\max(a_2, a_3) = 2$$$ 并删除 $$$a_3$$$。序列 $$$a$$$ 将变为 $$$[1, 2]$$$。
- 小猪可以选择 $$$i = 1$$$。然后他会将 $$$a_1$$$ 设置为 $$$\min(a_1, a_2) = 1$$$ 并删除 $$$a_2$$$。序列 $$$a$$$ 将变为 $$$[1]$$$。
- 序列的长度变为$$$1$$$,因此游戏将结束。 $$$a_1$$$ 的值最终将是 $$$1$$$。

在第四个测试用例中,可能的游戏流程之一如下:

- 最初 $$$a = [3, 1, 2, 2, 3]$$$。
- 海龟可以选择 $$$i = 4$$$。然后他会将 $$$a_4$$$ 设置为 $$$\max(a_4, a_5) = 3$$$ 并删除 $$$a_5$$$。序列 $$$a$$$ 将变为 $$$[3, 1, 2, 3]$$$。
- 小猪可以选择 $$$i = 3$$$。然后他会将 $$$a_3$$$ 设置为 $$$\min(a_3, a_4) = 2$$$ 并删除 $$$a_4$$$。序列 $$$a$$$ 将变为 $$$[3, 1, 2]$$$。
- 海龟可以选择 $$$i = 2$$$。然后他会将 $$$a_2$$$ 设置为 $$$\max(a_2, a_3) = 2$$$ 并删除 $$$a_3$$$。序列 $$$a$$$ 将变为 $$$[3, 2]$$$。
- 小猪可以选择 $$$i = 1$$$。然后他会将 $$$a_1$$$ 设置为 $$$\min(a_1, a_2) = 2$$$ 并删除 $$$a_2$$$。序列 $$$a$$$ 将变为 $$$[2]$$$。
- 序列的长度变为$$$1$$$,因此游戏将结束。 $$$a_1$$$ 的值最终将是 $$$2$$$。