题目描述

给定一个长度为 $n$ 的数组 $a$ 和一个数 $k$，其中 $0 \le k \le n$。

每次操作，你可以选择任意下标 $i$（$1 \le i \le n$），并将 $a_i$ 赋值为 $[0,n]$ 区间内的任意整数 $x$。

请你求出最少需要多少次操作，可以使得 $\operatorname{MEX}(a) = k$。

$\operatorname{MEX}$ 指的是一组数 $a_1,a_2,\dots,a_n$ 的最小未出现的非负整数。

输入格式

每组数据包含多组测试用例。

第一行包含一个整数 $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$），表示数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试用例，输出一个整数，表示满足 $\operatorname{MEX}(a)=k$ 所需的最小操作次数。

样例

5
1 0
0
3 1
0 2 3
5 5
0 1 2 3 4
6 2
0 3 4 2 6 2
7 4
0 1 5 4 4 7 3

1
0
0
2
2

样例说明

在第一个测试用例中，数组 $a=[0]$，所以 $\operatorname{MEX}=1$。
将 $0$ 替换为 $[1,n]$ 间的任意数，可使 $\operatorname{MEX}=0$。
因此，正好需要一次操作。

在第三个测试用例中，数组 $a$ 包含 $0,1,2,3,4$，所以一开始就有 $\operatorname{MEX}(a)=5$。

因为这正好等于要求的 $k$，所以无需操作，最少操作次数为 $0$。

由 ChatGPT 5 翻译

来源

Codeforces 2149C，英文题名 MEX rose。