数组 $$$b_1, b_2, \ldots b_m$$$ 的中位数,写作 $$$\operatorname{med}(b_1, b_2, \ldots, b_m)$$$,是 $$$\left\lceil \frac{m}{2} \right\rceil$$$-th$$$^{\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$$$。
输出
对于每个测试用例,输出“是“如果存在这样的分割,并且”NO”否则。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。
示例
输入复制
63 23 2 13 13 2 16 38 5 3 1 6 48 710 7 12 16 3 15 6 116 87 11 12 4 9 173 5000000001000 1000000000 1000
输出复制
YES NO NO YES YES YES
注意
在第一个和第二个测试用例中,将数组划分为三个连续子数组的唯一可能是 $$$[3]$$$、$$$[2]$$$、$$$[1]$$$。它们各自的中位数是 $$$3$$$、$$$2$$$ 和 $$$1$$$。三个子数组中位数的中位数为 $$$\operatorname{med}(3, 2, 1) = 2$$$。因此,第一个测试用例的答案是“是“因为 $$$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$$$,因此该分区满足约束。