У Монокарпа есть последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$. Он может выполнять со своей последовательностью следующую операцию неограниченное количество раз:
Перед вами стоит задача определить, может ли Монокарп с помощью некоторого (возможно нулевого) количества описанных операций сделать свою последовательность неубывающей (то есть, чтобы для всех $$$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]$$$). Таким образом, последовательность станет отсортированной по неубыванию.
Во втором примере последовательность изначально является неубывающей, поэтому никаких операций применять не нужно.
