E. Неподвижные точки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$. За один ход можно выбрать любой элемент последовательности и удалить его. Все элементы справа от удаленного сдвигаются на $$$1$$$ позицию влево, чтобы в последовательности не было пустых мест. Таким образом, за один ход длина последовательности всегда сокращается на $$$1$$$. Индексы элементов после хода пересчитываются.

Например, пусть последовательность имеет вид $$$a=[3, 2, 2, 1, 5]$$$. Допустим во время хода был выбран элемент $$$a_3=2$$$. Тогда после хода последовательность будет равна $$$a=[3, 2, 1, 5]$$$, причём теперь её $$$3$$$-м элементом будет считаться $$$a_3=1$$$, а $$$4$$$-м будет $$$a_4=5$$$.

Вам дана последовательность $$$a_1, a_2, \ldots, a_n$$$ и число $$$k$$$. Требуется найти минимальное количество ходов, которое нужно совершить, чтобы в последовательности не менее $$$k$$$ элементов были равны своим индексам, т. е. в полученной последовательности $$$b_1, b_2, \ldots, b_m$$$ существовало не менее $$$k$$$ индексов $$$i$$$ таких, что $$$b_i = i$$$.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

Каждый набор данных состоит из двух подряд идущих строк. Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2000$$$). Вторая строка содержит последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). Числа в последовательности не обязательно различны.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2000$$$.

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

Для каждого набора входных данных выведите в отдельной строке:

  • $$$-1$$$, если не существует искомой последовательности ходов;
  • в противном случае целое число $$$x$$$ ($$$0 \le x \le n$$$) — минимальное количество ходов, которое требуется, для того чтобы не менее $$$k$$$ элементов последовательности стали равны своим индексам.
Пример
Входные данные
4
7 6
1 1 2 3 4 5 6
5 2
5 1 3 2 3
5 2
5 5 5 5 4
8 4
1 2 3 3 2 2 5 5
Выходные данные
1
2
-1
2
Примечание

В первом наборе входных данных последовательность изначально не удовлетворяет виду, к которому её необходимо привести, однако, удалив первый элемент последовательности, можно добиться того, что последовательность примет вид $$$[1, 2, 3, 4, 5, 6]$$$, т. е. $$$6$$$ элементов будут равны своим индексам.

Во втором тестовом примере есть два способа достичь желаемого результата за $$$2$$$ хода: удалить $$$1$$$-й и $$$3$$$-й элементы, при этом последовательность будет иметь вид $$$[1, 2, 3]$$$, в которой будет $$$3$$$ равных своим индексам элемента; второй способ — удалить $$$2$$$-й и $$$3$$$-й элементы, тогда получится последовательность $$$[5, 2, 3]$$$, в которой будет $$$2$$$ искомых элемента.