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-----

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-----

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


-----Examples-----

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
Output
0
1
2
0


-----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]$.

Source: codeforces | Difficulty: HARD
Tags: Constructive algorithms

Sorting

Amortized analysis

Complete search

Greedy algorithms

Data structures


Solutions:
import heapq
import sys
input = sys.stdin.readline

def solve():
	(kvs, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	cnt = {}
	for num in arr:
		if num not in cnt:
			cnt[num] = 0
		cnt[num] += 1
	K = k
	x = kvs
	for i in range(kvs + 1):
		if i not in cnt:
			if K:
				K -= 1
			else:
				x = i
				break
	if x == kvs:
		return 0
	v = []
	for key in cnt:
		if key >= x:
			heapq.heappush(v, cnt[key])
	cost = len(v)
	while v:
		if v[0] <= k:
			k -= v[0]
			heapq.heappop(v)
			cost -= 1
		else:
			break
	return cost
for _ in range(int(input())):
	print(solve())


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	(n, k) = M()
	a = L()
	d = {}
	mx = 0
	for i in a:
		d[i] = d.get(i, 0) + 1
	while mx in d:
		mx += 1
	for i in range(k):
		mx += 1
		while mx in d:
			mx += 1
	l = sorted([i for i in set(a) if i > mx], key=lambda x: d[x])
	ans = len(l)
	for i in l:
		if k >= d[i]:
			k -= d[i]
			ans -= 1
	print(ans)


import heapq
from collections import Counter

def fuck(a, k):
	n = len(a)
	a.sort()
	(mex, last, i) = (0, k, 0)
	while i < n:
		if a[i] >= mex:
			gap = a[i] - mex
			if gap <= last:
				mex = a[i] + 1
				last -= gap
			else:
				mex += last
				break
		i += 1
	mp = Counter(a[i:])
	q = [mp[i] for i in mp]
	heapq.heapify(q)
	while len(q) > 0 and k > 0:
		t = heapq.heappop(q)
		if t > k:
			heapq.heappush(q, t - k)
			break
		else:
			k -= t
	return len(q)

def solve():
	T = int(input())
	for ii in range(T):
		(n, k) = map(int, input().split())
		line = input().split()
		a = []
		for s in line:
			a.append(int(s))
		print(fuck(a, k))
solve()


I = input
R = lambda : map(int, I().split())
for _ in range(int(I())):
	(n, k) = R()
	a = [*R()]
	c = {}
	mx = 0
	for v in a:
		c[v] = c.get(v, 0) + 1
	while mx in c:
		mx += 1
	for _ in range(k):
		mx += 1
		while mx in c:
			mx += 1
	b = sorted([v for v in set(a) if v > mx], key=lambda x: c[x])
	res = len(b)
	for v in b:
		if k >= c[v]:
			k -= c[v]
			res -= 1
		else:
			break
	print(res)


import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	aux_list = [0] * n
	for i in a:
		if i < n:
			aux_list[i] += 1
	mex = None
	for i in range(n):
		if aux_list[i] == 0:
			mex = i
			break
	if mex is None:
		print('0')
		continue
	left = k
	max_mex = None
	for i in range(n):
		if aux_list[i] == 0:
			if left > 0:
				left -= 1
			elif max_mex is None:
				max_mex = i
	if max_mex is None:
		max_mex = n
	s = dict({})
	for x in a:
		if x >= max_mex:
			if x not in s:
				s[x] = 0
			s[x] += 1
	L = []
	for x in s:
		L.append([s[x], x])
	L.sort()
	ans = len(L)
	for i in range(len(L)):
		if L[i][0] <= k:
			k -= L[i][0]
			ans -= 1
	print(ans)