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

Рассмотрим массив длины $$$n$$$, а также фиксированное целое число $$$m$$$. Операция покраски определяется следующим образом:

  • Выбрать отрезок длины $$$m$$$ и покрасить его значениями $$$1,2,\ldots,m$$$ слева направо.

    Формально, выбрать целое число $$$l$$$ такое, что $$$1\le l\le n-m+1$$$. Затем для каждого $$$1\le i\le m$$$ позиция $$$l+i-1$$$ красится значением $$$i$$$.

Если позиция покрашена несколько раз, сохраняется только значение, нанесённое последним.

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

Дан массив $$$a_1,a_2,\ldots,a_n$$$, где $$$1\le a_i\le m$$$. Найдите минимальное количество изменений, необходимых для того, чтобы сделать его допустимым. Одно изменение заменяет один элемент на любое целое число от $$$1$$$ до $$$m$$$.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1\le m\le n\le 5\cdot 10^5$$$) — длину массива и длину каждого закрашиваемого отрезка.

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

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

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

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

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

В преобразованиях ниже подчёркнутые позиции — это в точности позиции, покрашенные в последней операции.

В первом наборе входных данных массив уже является допустимым. Он может быть получен следующими операциями покраски: $$$$$$ [-,-,-,-,-]\to[-,-,\underline{1},\underline{2},\underline{3}]\to[\underline{1},\underline{2},\underline{3},2,3]. $$$$$$ Следовательно, никаких изменений не требуется, и ответ равен $$$0$$$.

Во втором наборе входных данных, так как $$$n=4$$$ и $$$m=3$$$, каждый допустимый массив должен быть получен покраской обоих отрезков $$$[1,3]$$$ и $$$[2,4]$$$. Например, $$$$$$ [-,-,-,-]\to[-,\underline{1},\underline{2},\underline{3}]\to[\underline{1},\underline{2},\underline{3},3]. $$$$$$ Это даёт допустимый массив $$$[1,2,3,3]$$$. Данный массив $$$[1,2,2,3]$$$ можно превратить в него, изменив только третий элемент, поэтому ответ равен $$$1$$$.

В третьем наборе входных данных один из ближайших допустимых массивов — $$$[1,1,2,3,3]$$$, который может быть получен следующим образом: $$$$$$ [-,-,-,-,-]\to[\underline{1},\underline{2},\underline{3},-,-]\to[1,2,\underline{1},\underline{2},\underline{3}]\to[1,\underline{1},\underline{2},\underline{3},3]. $$$$$$ Данный массив $$$[2,1,2,3,2]$$$ отличается от $$$[1,1,2,3,3]$$$ в двух позициях. Можно доказать, что одного изменения недостаточно, поэтому ответ равен $$$2$$$.