← 返回题目列表

Codeforces · 2169/A

A. 爱丽丝和鲍勃

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

Alice 和 Bob 有一个袋子,里面装着 $$$n$$$ 弹珠,第 $$$i$$$ 弹珠上写着整数 $$$v_i$$$。他们玩以下游戏:首先,每个玩家选择一个整数(让我们将 Alice 选择的整数表示为 $$$a$$$,将 Bob 选择的整数表示为 $$$b$$$)。之后,他们开始以任意顺序从袋子中取出弹珠,直到袋子空为止。对于每个球,分数将指向所选整数更接近弹珠上的整数的那个球; 如果平局,爱丽丝得分.

例如,如果 $$$a = 10$$$,$$$b = 30$$$,则

  • 对于整数 $$$10, 1, 7, 18, 20$$$ 和许多其他的弹珠,爱丽丝获得分数(请注意,她将获得弹珠 $$$20$$$ 的分数);
  • 对于整数 $$$59、25、30、21$$$ 和许多其他整数的大理石,Bob 获得了分数。

Bob 已经设法提前找出 Alice 会选择哪个整数。帮助他选择整数,使他获得的分数最大化。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成:

  • 第一行包含两个整数 $$$n$$$ 和 $$$a$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le a \le 10^9$$$)——分别是袋子里弹珠的数量和 Alice 选择的数量。
  • 第二行包含 $$$n$$$ 整数 $$$v_1, v_2, \dots, v_n$$$ ($$$1 \le v_1 \le v_2 \le \dots \le v_n \le 10^9$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 $$$b$$$ ($$$0 \le b \le 2 \cdot 10^9$$$),Bob 应选择该整数来最大化他收到的点数。如果有多个这样的数字,则可以输出其中任何一个。

示例

输入
复制

3
7 21
10 20 30 40 50 60 70
6 500
200 200 300 500 600 600
2 7
7 7

输出
复制

35
333
1337

注意

在第一个测试用例中,如果 Bob 选择 $$$35$$$,他会因为弹珠 $$$30, 40, 50, 60, 70$$$ 获得 $$$5$$$ 点。

在第三个测试用例中,无论 Bob 选择哪个整数,他都会获得 $$$0$$$ 分。