← 返回题目列表

Codeforces · 1349/B

B. Orac 和中值

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

Slime 有一个正整数序列 $$$a_1, a_2, \ldots, a_n$$$。

在一次操作中,Orac 可以选择该序列的任意子段 $$$[l \ldots r]$$$ 并将所有值 $$$a_l, a_{l + 1}, \ldots, a_r$$$ 替换为 $$$\{a_l, a_{l + 1}, \ldots, a_r\}$$$ 的中值。

在这个问题中,对于整数多重集 $$$s$$$,$$$s$$$ 的中位数等于其中 $$$\lfloor \frac{|s|+1}{2}\rfloor$$$ 中的第一个最小数。例如,$$$\{1,4,4,6,5\}$$$ 的中位数为 $$$4$$$,$$$\{1,7,5,8\}$$$ 的中位数为 $$$5$$$。

Slime 希望 Orac 使用这些操作来生成 $$$a_1 = a_2 = \ldots = a_n = k$$$。

Orac认为这是不可能的,他不想浪费时间,所以他决定问你是否可以满足史莱姆的要求,他可能会问你几次这些问题。

输入

第一行输入的是单个整数$$$t$$$:查询次数。

每个查询的第一行包含两个整数 $$$n\ (1\le n\le 100\,000)$$$ 和 $$$k\ (1\le k\le 10^9)$$$,第二行包含 $$$n$$$ 正整数 $$$a_1,a_2,\dots,a_n\ (1\le a_i\le 10^9)$$$

$$$n$$$ 的总和最多为 $$$100\,000$$$。

输出

输出应包含 $$$t$$$ 行。如果可以在一定次数的操作中使所有整数 $$$k$$$ 成为可能,则第 $$$i$$$ 行应等于“yes”,否则应等于“no”。您可以以小写或大写形式打印每个字母。

示例

输入 #1

5
5 3
1 5 2 6 1
1 6
6
3 2
1 2 3
4 3
3 1 2 3
10 3
1 2 3 4 5 6 7 8 9 10

输出 #1

no
yes
yes
no
yes

注意

在第一个查询中,Orac 无法将所有元素转换为 $$$3$$$。

在第二个查询中,$$$a_1=6$$$ 已经满足。

在第三个查询中,Orac可以选择完整的数组并将所有元素变成$$$2$$$。

在第四个查询中,Orac 无法将所有元素都转换为 $$$3$$$。

在第五个查询中,Orac可以先选择$$$[1,6]$$$,然后选择$$$[2,10]$$$。