Codeforces Round 912 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

greedy

sortings

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Halloumi Boxes

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTheofanis 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.

Example

Input

53 21 2 33 19 9 94 46 4 2 14 310 3 830 142 13 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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2024 05:06:57 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|