MEX vs DIFF
Contest: Codeforces Round 792 (Div. 1 + Div. 2)
Difficulty rating: 2100
Tags: binary search, brute force, constructive algorithms, data structures, greedy, two pointers

You are given an array $$$a$$$ of $$$n$$$ non-negative integers. In one operation you can change any number in the array to any other non-negative integer.

Let's define the cost of the array as $$$\operatorname{DIFF}(a) - \operatorname{MEX}(a)$$$, where $$$\operatorname{MEX}$$$ of a set of non-negative integers is the smallest non-negative integer not present in the set, and $$$\operatorname{DIFF}$$$ is the number of different numbers in the array.

For example, $$$\operatorname{MEX}(\{1, 2, 3\}) = 0$$$, $$$\operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3$$$.

You should find the minimal cost of the array $$$a$$$ if you are allowed to make at most $$$k$$$ operations.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le k \le 10^5$$$) — the length of the array $$$a$$$ and the number of operations that you are allowed to make.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case output a single integer — minimal cost that it is possible to get making at most $$$k$$$ operations.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case no operations are needed to minimize the value of $$$\operatorname{DIFF} - \operatorname{MEX}$$$.

In the second test case it is possible to replace $$$5$$$ by $$$1$$$. After that the array $$$a$$$ is $$$[0,\, 2,\, 4,\, 1]$$$, $$$\operatorname{DIFF} = 4$$$, $$$\operatorname{MEX} = \operatorname{MEX}(\{0, 1, 2, 4\}) = 3$$$, so the answer is $$$1$$$.

In the third test case one possible array $$$a$$$ is $$$[4,\, 13,\, 0,\, 0,\, 13,\, 1,\, 2]$$$, $$$\operatorname{DIFF} = 5$$$, $$$\operatorname{MEX} = 3$$$.

In the fourth test case one possible array $$$a$$$ is $$$[1,\, 2,\, 3,\, 0,\, 0,\, 0]$$$.

Example input:
4
4 1
3 0 1 2
4 1
0 2 4 5
7 2
4 13 0 0 13 1337 1000000000
6 2
1 2 8 0 0 0

Example output:
0
1
2
0

Editorial:
Let's consider all possible $$$\operatorname{MEX}$$$ after all operations. It is from $$$0$$$ to $$$n$$$ and we can check them all in the increasing order. Now let's fix some $$$\operatorname{MEX} = m$$$. There should be all numbers from $$$0$$$ to $$$m$$$ in the array, so there are some "holes" in the array that should be covered. The hole is an integer from $$$0$$$ to $$$m$$$ which is not present in the array. If there is at least one hole in the end it is not possible to obtain $$$\operatorname{MEX} = m$$$.
Now let's see how we should cover the holes. We will do it greedily. Firstly, we will need to use integers that are greater than $$$m$$$. It is easy to see that they are always not worse to use than the integers which are already from $$$0$$$ to $$$m$$$. Moreover, we should start from those integers that occur less times in the array. It is because each time we cover a hole we increase $$$\operatorname{MEX}$$$ at least by one (we cover the holes in increasing order) and the value of $$$\operatorname{DIFF}$$$ increases at most by $$$1$$$ and it does not increase when we change the last element of the same value.
After that if we used all integers that are greater than $$$m$$$ we should use those integers that are from $$$0$$$ to $$$m$$$ but only those that occur more than once. By doing these operations we increase $$$\operatorname{MEX}$$$ at least by $$$1$$$ and increase $$$\operatorname{DIFF}$$$ exactly by $$$1$$$ (because we cover a hole).
Now let's notice that when considering each $$$\operatorname{MEX}$$$ value in the increasing order we can simply maintain some information about the current state of the array: a set that helps us find the elements greater than $$$m$$$ which occur less times in the array, the amount of not covered holes, the number of "bonus" elements from $$$0$$$ to $$$m$$$ (the number of integers from $$$0$$$ to $$$m$$$ minus $$$\operatorname{DIFF}$$$ from those elements that are from $$$0$$$ to $$$m$$$) and it is easy to see how it is changed when we increase $$$\operatorname{MEX}$$$. So in total we can calculate the answer for each $$$\operatorname{MEX}$$$ for all $$$\operatorname{MEX}$$$ from $$$0$$$ to $$$n$$$.