← 返回题目列表

Codeforces · 1592/B

B. Hemose 购物

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

Hemose 与他的朋友 Samez、AhmedZ、AshrafEzz、TheSawan 和 O_E 在德国购物。如你所知,Hemose 和他的朋友们都是问题解决者,所以他们非常聪明。因此,他们会去德国所有的折扣市场。

Hemose 有一个 $$$n$$$ 整数数组。他希望 Samez 按非降序对数组进行排序。由于这对于 Samez 来说是一个太简单的问题,Hemose 允许 Samez 仅使用以下操作:

- 选择索引 $$$i$$$ 和 $$$j$$$,使得 $$$1 \le i、j \le n$$$ 和 $$$\lvert i - j \rvert \geq x$$$。然后,交换元素 $$$a_i$$$ 和 $$$a_j$$$。

你能告诉 Samez 是否有一种方法可以通过使用上面编写的有限次数的操作(可能是 $$$0$$$)来按非降序对数组进行排序?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ $$$(1 \leq t \leq 10^5)$$$。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ $$$(1 \leq x \leq n \leq 10^5)$$$。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, ..., a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$。

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

输出

对于每个测试用例,您应该输出一个字符串。

如果 Samez 可以使用上面编写的操作以非降序对数组进行排序,则输出“YES”(不带引号)。否则,输出“NO”(不带引号)。

您可以以任何大小写(大写或小写)打印“YES”和“NO”的每个字母。

示例

输入 #1

4
3 3
3 2 1
4 3
1 2 3 4
5 2
5 1 2 3 4
5 4
1 2 3 4 4

输出 #1

NO
YES
YES
YES

注意

在第一个测试用例中,您不能执行任何操作。

在第二个测试用例中,数组已经排序。

在第三个测试用例中,可以进行如下操作:

- $$$[5,1,2,3,4]$$$,$$$交换(a_1,a_3)$$$
- $$$[2,1,5,3,4]$$$,$$$交换(a_2,a_5)$$$
- $$$[2,4,5,3,1]$$$, $$$交换(a_2,a_4)$$$
- $$$[2,3,5,4,1]$$$, $$$交换(a_1,a_5)$$$
- $$$[1,3,5,4,2]$$$, $$$交换(a_2,a_5)$$$
- $$$[1,2,5,4,3]$$$,$$$交换(a_3,a_5)$$$
- $$$[1,2,3,4,5]$$$

(这里$$$swap(a_i, a_j)$$$指的是交换位置$$$i$$$,$$$j$$$处的元素)。