310872: CF1903A. Halloumi Boxes

A. Halloumi Boxestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Theofanis is busy after his last contest, as now, he has to deliver many halloumis all over the world. He stored them inside $n$ boxes and each of which has some number $a_i$ written on it.

He wants to sort them in non-decreasing order based on their number, however, his machine works in a strange way. It can only reverse any subarray$^{\dagger}$ of boxes with length at most $k$.

Find if it's possible to sort the boxes using any number of reverses.

$^{\dagger}$ Reversing a subarray means choosing two indices $i$ and $j$ (where $1 \le i \le j \le n$) and changing the array $a_1, a_2, \ldots, a_n$ to $a_1, a_2, \ldots, a_{i-1}, \; a_j, a_{j-1}, \ldots, a_i, \; a_{j+1}, \ldots, a_{n-1}, a_n$. The length of the subarray is then $j - i + 1$.

Input

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases.

Each test case consists of two lines.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 100$) — the number of boxes and the length of the maximum reverse that Theofanis can make.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{9}$) — the number written on each box.

Output

For each test case, print YES (case-insensitive), if the array can be sorted in non-decreasing order, or NO (case-insensitive) otherwise.

ExampleInput

5
3 2
1 2 3
3 1
9 9 9
4 4
6 4 2 1
4 3
10 3 830 14
2 1
3 1

Output

YES
YES
YES
YES
NO

Note

In the first two test cases, the boxes are already sorted in non-decreasing order.

In the third test case, we can reverse the whole array.

In the fourth test case, we can reverse the first two boxes and the last two boxes.

In the fifth test case, it can be shown that it's impossible to sort the boxes.

题目大意：
Theofanis 在上一次比赛之后很忙，因为他现在需要把许多 halloumi（一种奶酪）运送到世界各地。他把它们存放在 n 个盒子里，每个盒子上都写有一些数字 a_i。他想要根据这些数字将盒子们非降序排序，但是他的机器工作方式很奇怪，它只能反转长度最多为 k 的任意子数组。需要找出是否可以通过任意数量的反转来排序这些盒子。

输入输出数据格式：
输入：
- 第一行包含一个整数 t（1 ≤ t ≤ 100）——测试用例的数量。
- 每个测试用例包含两行。
- 第一行包含两个整数 n 和 k（1 ≤ k ≤ n ≤ 100）——盒子的数量和 Theofanis 可以进行的最大反转长度。
- 第二行包含 n 个整数 a_1, a_2, ..., a_n（1 ≤ a_i ≤ 10^9）——每个盒子上的数字。

输出：
- 对于每个测试用例，如果数组可以按非降序排序，则打印 YES（大小写不敏感），否则打印 NO（大小写不敏感）。题目大意： Theofanis 在上一次比赛之后很忙，因为他现在需要把许多 halloumi（一种奶酪）运送到世界各地。他把它们存放在 n 个盒子里，每个盒子上都写有一些数字 a_i。他想要根据这些数字将盒子们非降序排序，但是他的机器工作方式很奇怪，它只能反转长度最多为 k 的任意子数组。需要找出是否可以通过任意数量的反转来排序这些盒子。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1 ≤ t ≤ 100）——测试用例的数量。 - 每个测试用例包含两行。 - 第一行包含两个整数 n 和 k（1 ≤ k ≤ n ≤ 100）——盒子的数量和 Theofanis 可以进行的最大反转长度。 - 第二行包含 n 个整数 a_1, a_2, ..., a_n（1 ≤ a_i ≤ 10^9）——每个盒子上的数字。 输出： - 对于每个测试用例，如果数组可以按非降序排序，则打印 YES（大小写不敏感），否则打印 NO（大小写不敏感）。