E. d-сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$. Он может выполнять со своей последовательностью следующую операцию неограниченное количество раз:

  • выбрать две позиции $$$i$$$ и $$$j$$$ ($$$i \lt j$$$), находящиеся на расстоянии $$$d$$$ друг от друга (то есть $$$j - i = d$$$), и поменять местами значения в этих позициях, то есть поменять местами $$$a_i$$$ и $$$a_j$$$.

Перед вами стоит задача определить, может ли Монокарп с помощью некоторого (возможно нулевого) количества описанных операций сделать свою последовательность неубывающей (то есть, чтобы для всех $$$i$$$ от $$$1$$$ до $$$n - 1$$$ было верно, что $$$a_i \le a_{i + 1}$$$).

Входные данные

В первой строке следуют два целых числа $$$n$$$ и $$$d$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le d \le n - 1$$$) — количество элементов в последовательности и расстояние, на котором должны находится элементы последовательности для обмена в ходе операций.

Во второй строке следуют $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — описание последовательности Монокарпа.

Выходные данные

Если Монокарп может сделать свою последовательность неубывающей с помощью описанных операций, выведите «YES» (без кавычек). В противном случае, выведите «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
Примечание

В первом примере можно с помощью одной операции поменять первый и третий элементы (после этого последовательность станет равна $$$[1, 7, 6, 4]$$$), а затем с помощью еще одной операции поменять второй и четвертый элементы (после этого последовательность станет равна $$$[1, 4, 6, 7]$$$). Таким образом, последовательность станет отсортированной по неубыванию.

Во втором примере последовательность изначально является неубывающей, поэтому никаких операций применять не нужно.