Codeforces Round 746 (Div. 2) |
---|
Закончено |
Хемосе вместе со своими друзьями Самезом, Ахмедом, Ашрафом, Саваном и О_Е ходил по магазинам в Германии. Как вы знаете, Хемосе и его друзья решают задачи, поэтому они очень умны. Поэтому они отправятся во все магазины со скидками в Германии.
У Хемосе есть массив из $$$n$$$ целых чисел. Он хочет, чтобы Самез отсортировал массив в неубывающем порядке. Поскольку для Самеза это было бы слишком простой задачей, Хемосе разрешает Самезу использовать только следующую операцию:
Выберите индексы $$$i$$$ и $$$j$$$ такие, что $$$1 \le i, j \le n$$$, и $$$\lvert i - j \rvert \geq x$$$. Затем поменяйте местами элементы $$$a_i$$$ и $$$a_j$$$.
Подскажите, пожалуйста, существует ли способ отсортировать массив в неубывающем порядке, используя вышеописанную операцию некоторое конечное число раз (возможно, $$$0$$$)?
Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ $$$(1 \leq t \leq 10^5)$$$. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ $$$(1 \leq x \leq n \leq 10^5)$$$.
Вторая строка каждого наборов входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, ..., a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных необходимо вывести одну строку.
Если Самез может отсортировать массив в неубывающем порядке с помощью операции, описанной выше, выведите «YES» (без кавычек). В противном случае выведите «NO» (без кавычек).
Вы можете вывести каждую букву «YES» и «NO» в любом регистре (верхнем или нижнем).
4 3 3 3 2 1 4 3 1 2 3 4 5 2 5 1 2 3 4 5 4 1 2 3 4 4
NO YES YES YES
В первом наборов входных данных вы не можете выполнить никаких операций.
Во втором наборе входных данных массив уже отсортирован.
В третьем наборе входных данных вы можете выполнить следующие операции:
(Здесь под $$$swap(a_i, a_j)$$$ имеется в виду обмен местами элементов на позициях $$$i$$$, $$$j$$$).
Название |
---|