Дан массив $$$a$$$ длины $$$n$$$ и число $$$k$$$, где $$$0 \le k \le n$$$.
За одну операцию можно выбрать произвольный индекс $$$i$$$ ($$$1 \le i \le n$$$) и присвоить $$$a_i$$$ любое целое значение $$$x$$$ из диапазона $$$[0,n]$$$.
Найдите минимальное количество таких операций, после которых выполнится условие: $$$\operatorname{MEX}(a)$$$$$$^{\text{∗}}$$$$$$=k$$$
$$$^{\text{∗}}$$$Наименьшее исключённое (MEX) набора чисел $$$a_1,a_2,\dots,a_n$$$ — это минимальное неотрицательное целое $$$x$$$, которое не встречается среди $$$a_i$$$.
Каждый тест состоит из нескольких наборов входных данных.
В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5,\,\, 0 \le k \le n$$$) — длина массива $$$a$$$ и требуемый $$$\operatorname{MEX}(a)$$$.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$0 \le a_i \le n$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для выполнения условия $$$\operatorname{MEX}(a)=k$$$.
51 003 10 2 35 50 1 2 3 46 20 3 4 2 6 27 40 1 5 4 4 7 3
10022
В первом наборе входных данных массив $$$a=[0]$$$, поэтому $$$\operatorname{MEX}=1$$$.$$$ \\ $$$Убрав ноль (переписав его на любое $$$x\in[1,n]$$$), получаем $$$\operatorname{MEX}=0$$$. $$$ \\ $$$Значит, требуется ровно одна операция.
В третьем наборе входных данных в массиве присутствуют все числа $$$0,1,2,3,4$$$, поэтому $$$\operatorname{MEX}(a)=5$$$ уже изначально.
Поскольку это совпадает с требуемым $$$k$$$, изменения не нужны и минимальное число операций равно $$$0$$$.
| Codeforces Round 1054 (Div. 3) |
|---|
| Закончено |
