F1. Сервал и цветной массив (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n\le 3000$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

У Сервала есть магическое число $$$k$$$ ($$$k\ge 2$$$). Назовём массив $$$r$$$ цветным, если и только если:

  • Длина $$$r$$$ равна $$$k$$$, и
  • Каждое целое число от $$$1$$$ до $$$k$$$ встречается ровно один раз в $$$r$$$.

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

  • Выбрать индекс $$$i$$$ ($$$1\le i \lt n$$$), затем поменять местами $$$a_i$$$ и $$$a_{i+1}$$$.

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

$$$^{\text{∗}}$$$Массив $$$b$$$ является подмассивом массива $$$a$$$, если $$$b$$$ может быть получен из $$$a$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2\leq k\leq n\leq 3000$$$) — длина массива $$$a$$$ и магическое число Сервала.

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

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

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

Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для того, чтобы сделать хотя бы один подмассив массива $$$a$$$ цветным.

Пример
Входные данные
6
3 2
1 2 1
7 3
2 1 1 3 1 1 2
6 3
1 1 2 2 2 3
6 3
1 2 2 2 2 3
10 5
5 1 3 1 1 2 2 4 1 3
9 4
1 2 3 3 3 3 3 2 4
Выходные данные
0
1
2
3
4
5
Примечание

В первом наборе входных данных, поскольку подмассивы $$$[a_1, a_2] = [1, 2]$$$ и $$$[a_2, a_3] = [2, 1]$$$ уже цветные, нам не нужно выполнять никаких операций. Таким образом, ответ равен $$$0$$$.

Во втором наборе входных данных мы можем поменять местами $$$a_1$$$ и $$$a_2$$$, чтобы получить $$$[1, \underline{2, 1, 3}, 1, 1, 2]$$$, который имеет цветной подмассив $$$[a_2, a_3, a_4] = [2, 1, 3]$$$. И данный массив изначально не имеет никаких цветных подмассивов, поэтому ответ равен $$$1$$$.