B. Ещё одна задача на MEX
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$ и целое число $$$k$$$. Пусть $$$f(l,r)$$$ — это значение $$$\operatorname{mex}(a_l,a_{l+1},\ldots,a_r)$$$$$$^{\text{∗}}$$$. Вы хотите выполнить следующую операцию $$$n-k+1$$$ раз:

  • Пусть текущая длина массива равна $$$|a|$$$. Вам нужно найти подмассив $$$[l, r]$$$ длины $$$k$$$ такой, что $$$\operatorname{max}_{i=1}^{|a|-k+1} f(i, i+k-1) = f(l, r).$$$ Другими словами, вам нужно выбрать окно из $$$k$$$ элементов, такое что среди всех окон размером $$$k$$$ выбранное вами окно имеет максимальный $$$\operatorname{mex}$$$. Если существует несколько $$$[l,r]$$$, вы можете выбрать любое. Затем вы должны выбрать любое целое число $$$i$$$ такое, что $$$l \leq i \leq r$$$, и удалить $$$a_i$$$ из $$$a$$$. То есть ваш новый массив будет $$$[a_1, a_2, \ldots, a_{i-1}, a_{i+1}, a_{i+2}, \ldots, a_n]$$$.

Например, в массиве $$$[1,2,0,1,3,0]$$$ с $$$k=3$$$ две возможные пары $$$(l,r)$$$ — это $$$(1,3)$$$ и $$$(2,4)$$$ (так как у них обоих $$$\operatorname{mex} 3$$$, что является максимумом среди всех окон размером $$$3$$$). Следовательно, вы можете удалить любой из индексов $$$1,2,3,4$$$ на вашем следующем ходу.

После $$$n - k + 1$$$ операций у вас останется последовательность длины $$$k-1$$$. Ваша цель — максимизировать $$$\operatorname{mex}$$$ оставшихся элементов. Найдите максимальный возможный $$$\operatorname{mex}$$$.

$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$.

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

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

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

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

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

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

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

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

В первом наборе входных данных мы можем выбрать подмассив $$$[1,3]$$$. Из него удаляем $$$a_2$$$, чтобы получить $$$[0,0]$$$. Процесс завершается, и $$$\operatorname{mex}$$$ оставшихся элементов равен $$$1$$$.

В третьем наборе входных данных мы можем выполнить следующие операции:

  • Выбрать $$$i=1,j=3$$$. Это корректно, потому что $$$\operatorname{mex}$$$ всех окон размером $$$3$$$ равен $$$3,0,3$$$, и окно $$$[1,3]$$$ имеет $$$\operatorname{mex}$$$ равный $$$3$$$, что является максимумом. Затем удаляем $$$a_2$$$. Массив теперь равен $$$[0,2,1,0]$$$.
  • Выбрать $$$i=2,j=4$$$. Затем удаляем $$$a_2$$$. Массив теперь равен $$$[0,1,0]$$$.
  • Выбрать $$$i=1,j=3$$$. Затем удаляем $$$a_1$$$. Массив теперь равен $$$[1,0]$$$. Процесс завершается, и финальный $$$\operatorname{mex}$$$ равен $$$2$$$.