410250: GYM103993 E d-Sort

Monocarp has got a sequence of integers $$$a_1, a_2, \dots, a_n$$$. He can perform the following operation any number of times:

• choose two indices $$$i$$$ and $$$j$$$ ($$$i < j$$$) having distance exactly $$$d$$$ (i. e. $$$j - i = d$$$), and swap the corresponding elements of the sequence, i. e. swap $$$a_i$$$ and $$$a_j$$$.

You have to determine if it is possible to sort the sequence in non-descending order (i. e. reorder the elements so that for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$, the condition $$$a_i \le a_{i + 1}$$$ is met) using the described operation any number of times (possibly zero).

The first line contains two integers $$$n$$$ and $$$d$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le d \le n - 1$$$) — the number of elements in the sequence and the distance for the swap operation, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — the elements of the sequence.

If it's possible to sort the sequence in non-descending order using the described operation any number of times, print YES. Otherwise, print NO.

4 2
6 7 1 4

YES

5 3
5 6 6 10 10

YES

8 3
4 5 3 1 3 4 2 4

NO

In the first example, it's possible to swap the first element and the third element (the sequence becomes $$$[1, 7, 6, 4]$$$), and then swap the second element and the fourth element (so the sequence becomes $$$[1, 4, 6, 7]$$$). After that, the sequence is sorted in non-descending order.

In the second example, the sequence is already sorted in non-descending order.