D. Сделайте палиндром
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ размером $$$n$$$ и целое число $$$k$$$. Вы можете выполнить следующую операцию любое количество раз:

  • Выберите два целых числа $$$l$$$ и $$$r$$$ $$$(1 \le l \le r \le |a|)$$$ таких, чтобы $$$r-l+1 \geq k$$$.
  • Затем выберите индекс $$$i$$$ такой, что $$$l\leq i \leq r$$$, где $$$a_i$$$ является $$$k$$$-м по величине числом из подмассива $$$[a_l,a_{l+1},\ldots,a_r]$$$. Если есть несколько возможных $$$i$$$, вы можете выбрать любое. Например, рассмотрим $$$a = [1, 2, 2, 1, 3], l = 1, r = 5$$$ и $$$k = 3$$$, тогда возможные значения $$$i$$$ — индексы $$$2$$$ и $$$3$$$.
  • Затем удалите $$$a_i$$$ из $$$a$$$, соединяя оставшиеся части массива.

Определите, возможно ли получить массив, который является палиндромом$$$^{\text{∗}}$$$ после применения операции какое-то число раз. Обратите внимание, что пустой массив считается палиндромом.

$$$^{\text{∗}}$$$Массив $$$b=[b_1,b_2,\ldots,b_m]$$$ является палиндромом, если для каждого $$$1 \leq i \leq m$$$, $$$b_i=b_{m+1-i}$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 2\cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите YES, если возможно создать палиндром, и NO в противном случае. Вы можете выводить в любом регистре (верхнем или нижнем). Например, строки "yEs", "yes", "Yes" и "YES" будут распознаны как положительные ответы.

Пример
Входные данные
8
5 3
5 4 3 4 5
4 1
1 1 2 1
6 6
2 3 4 5 3 2
5 4
5 2 4 3 1
8 5
4 7 1 2 3 1 3 4
5 4
1 2 1 2 2
3 3
1 2 2
4 4
2 1 2 2
Выходные данные
YES
YES
YES
NO
NO
YES
NO
YES
Примечание

В первом наборе входных данных $$$a$$$ уже является палиндромом.

Во втором наборе входных данных мы можем выполнить две операции следующим образом: $$$[\mathbf{1,1},2,1]\rightarrow [1,\mathbf{2},1]\rightarrow[1,1]$$$

В третьем наборе входных данных мы можем выполнить одну операцию следующим образом: $$$[\mathbf{2,3,4,5,3,2}]\rightarrow[2,3,4,3,2]$$$.

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