C. Медианные разбиения
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Медиана массива $$$b_1, b_2, \ldots b_m$$$, обозначаемая $$$\operatorname{med}(b_1, b_2, \ldots, b_m)$$$, является $$$\left\lceil \frac{m}{2} \right\rceil$$$-м$$$^{\text{∗}}$$$ элементом массива $$$b$$$ в порядке возрастания.

Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ и целое число $$$k$$$. Вам необходимо определить, существует ли пара индексов $$$1 \le l \lt r \lt n$$$ такая, что:

$$$$$$\operatorname{med}(\operatorname{med}(a_1, a_2, \ldots, a_l), \operatorname{med}(a_{l+1}, a_{l+2}, \ldots, a_r), \operatorname{med}(a_{r+1}, a_{r+2}, \ldots, a_n)) \le k.$$$$$$

Другими словами, определите, возможно ли разбить массив на три непрерывных подмассива$$$^{\text{†}}$$$ так, чтобы медиана трех медиан подмассивов была меньше или равна $$$k$$$.

$$$^{\text{∗}}$$$$$$\lceil x \rceil$$$ это функция потолка, которая возвращает наименьшее целое число, большее или равное $$$x$$$.

$$$^{\text{†}}$$$Массив $$$x$$$ является подмассивом массива $$$y$$$, если $$$x$$$ может быть получен из $$$y$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — длина массива $$$a$$$ и константа $$$k$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если искомое разбиение существует, и «NO», в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
6
3 2
3 2 1
3 1
3 2 1
6 3
8 5 3 1 6 4
8 7
10 7 12 16 3 15 6 11
6 8
7 11 12 4 9 17
3 500000000
1000 1000000000 1000
Выходные данные
YES
NO
NO
YES
YES
YES
Примечание

В первом и втором наборах входных данных единственное возможное разбиение массива на три непрерывных подмассива — это $$$[3]$$$, $$$[2]$$$, $$$[1]$$$. Их медианы соответственно равны $$$3$$$, $$$2$$$ и $$$1$$$. Медиана трех медиан подмассивов равна $$$\operatorname{med}(3, 2, 1) = 2$$$. Поэтому ответ для первого набора входных данных — «YES», так как $$$2\le 2$$$, в то время как ответ для второго набора — «NO», так как $$$2 \gt 1$$$.

В третьем наборе входных данных можно доказать, что ни одно разбиение не удовлетворяет условиям.

В четвертом наборе входных данных одно из разбиений, удовлетворяющее условиям, — это $$$[10, 7]$$$, $$$[12, 16, 3, 15]$$$, $$$[6, 11]$$$. Соответствующие медианы подмассивов равны $$$7$$$, $$$12$$$ и $$$6$$$. Медиана трех медиан подмассивов равна $$$\operatorname{med}(7, 12, 6) = 7 \le k$$$, следовательно, это разбиение удовлетворяет условиям.

В пятом наборе входных данных одно из разбиений, удовлетворяющих условиям, — это $$$[7, 11]$$$, $$$[12, 4]$$$, $$$[9, 17]$$$. Соответствующие медианы подмассивов равны $$$7$$$, $$$4$$$ и $$$9$$$. Медиана трех медиан подмассивов равна $$$\operatorname{med}(7, 4, 9) = 7 \le k$$$, следовательно, это разбиение удовлетворяет условиям.

В шестом наборе входных данных единственное возможное разбиение массива на три непрерывных подмассива — это $$$[1000]$$$, $$$[10^9]$$$, $$$[1000]$$$. Соответствующие медианы подмассивов равны $$$1000$$$, $$$10^9$$$ и $$$1000$$$. Медиана трех медиан подмассивов равна $$$\operatorname{med}(1000, 10^9, 1000) = 1000 \le k$$$, следовательно, это разбиение удовлетворяет условиям.