E. d-Sort
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \lt 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).

Input

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.

Output

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.

Examples
Input
4 2
6 7 1 4
Output
YES
Input
5 3
5 6 6 10 10
Output
YES
Input
8 3
4 5 3 1 3 4 2 4
Output
NO
Note

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.