Read problems statements in mandarin chinese, russian and vietnamese as well. 

You are given a multi-set S of N integers, and an integer K. You want to find the maximum value of minimal excluded non-negative integer (MEX) of the multi-set given that you are allowed to add at most any K integers to the multi-set. Find the maximum value of MEX that you can obtain. 

Few examples of finding MEX of a multi-set are as follows. MEX of multi-set {0} is 1, {1} is 0, {0, 1, 3} is 2, {0, 1, 2, 3, 5, 6} is 4.

------ Input ------ 

The first line of the input contains an integer T denoting the number of testcases.

The first line of each test case contains two space seperated integers N and K denoting the size of the multi-set and the maximum number of extra integers that you can add in the multi-set respectively.

The second line contains N space separated integers denoting the multi-set S: S_{1}, S_{2} ,.... S_{N}.

------ Output ------ 

For each testcase, output the answer in a single line. 

------ Constraints ------ 

1 ≤ T ≤ 10
1 ≤ N ≤ 10^{5}
0 ≤ K ≤ 10^{5}
0 ≤ S_{i} ≤ 2 * 10^{5}

------ Subtasks ------ 

Subtask #1 (15 points): K=0.
Subtask #2 (85 points): Original Constraints.

----- Sample Input 1 ------ 
4

3 0

1 0 2

3 1

1 0 2

4 3

2 5 4 9

2 0

3 4
----- Sample Output 1 ------ 
3

4

6

0
----- explanation 1 ------ 
Example case 1. As K = 0, so we can't add any element to the multi-set. Elements of the set are {1, 0, 2}. The MEX value of this set is 3.
Example case 2. As K = 1, you are allowed to add at most 1 element to the multi-set. The multi-set are {1, 0, 2}. You can add element 3 to the multi-set, and it becomes {1, 0, 2, 3}. The MEX value of this multi-set is 4. There is no other way to have higher value of MEX of the set by adding at most one element to the multi-set.

Source: codechef | Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms


Solutions:
for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	s.sort()
	r = 0
	a = []
	x = 0
	flag = 0
	if s[0] != 0:
		if k >= s[0]:
			k -= s[0]
		else:
			flag = 1
			r = k
	if flag == 0:
		for j in range(0, len(s) - 1):
			if s[j + 1] - s[j] > 1:
				if k >= s[j + 1] - s[j] - 1:
					k -= s[j + 1] - s[j] - 1
					x = j
				else:
					x = j
					break
			x = j
			if j == len(s) - 2:
				x += 1
		r = s[x] + k + 1
	print(r)


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = sorted(list(map(int, input().split())))
	max_len = [x for x in range(max(s) + k + 2)]
	result = sorted(list(Counter(max_len) - Counter(s)))
	print(result[k])


from collections import Counter as C
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	s = list(map(int, input().split(' ')))
	print(sorted(list(C([i for i in range(max(s) + k + 2)]) - C(s)))[k])


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = set(list(map(int, input().split())))
	value = 0
	while True:
		if value not in s:
			if k == 0:
				break
			else:
				k -= 1
				value += 1
		else:
			value += 1
	print(value)


from collections import *
from math import *
from sys import *
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = set(list(map(int, input().split())))
	value = 0
	while True:
		if value not in arr:
			if k == 0:
				break
			else:
				k -= 1
				value += 1
		else:
			value += 1
	print(value)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = set(list(map(int, input().split())))
	l = k
	for i in range(n + k + 1):
		if i in arr:
			pass
		elif l > 0:
			l -= 1
		else:
			print(i)
			break


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	s.sort()
	l = -1
	for i in s:
		diff = i - l
		if diff > 1:
			if diff - 1 <= k:
				k -= diff - 1
			else:
				print(l + k + 1)
				break
		l = i
	else:
		print(s[n - 1] + k + 1)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	s = set(list(map(int, input().split())))
	mex = 0
	while True:
		if mex in s:
			mex += 1
		elif K > 0:
			K -= 1
			mex += 1
		else:
			break
	print(mex)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l = set(l)
	sample = [i for i in range(max(l) + k + 2)]
	for i in sample:
		if i not in l and k != 0:
			l.add(i)
			k -= 1
		elif i not in l and k == 0:
			print(i)
			break


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = list(map(int, input().split()))
	Z = []
	for i in range(0, max(S) + 1):
		Z.append(i)
	S.sort()
	Z.sort()
	S = set(S)
	Z = set(Z)
	Y = list(Z - Z.intersection(S))
	if K <= len(Y) - 1:
		print(Y[K])
	else:
		print(max(S) + K + 1 - len(Y))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = set(map(int, input().split()))
	last = n + k
	for i in range(n + k):
		if i not in arr:
			if k > 0:
				k -= 1
			else:
				last = i
				break
	print(last)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = set(map(int, input().split()))
	i = 0
	while True:
		if i not in arr and k == 0:
			break
		elif i not in arr and k > 0:
			k -= 1
		i += 1
	print(i)


from sys import stdin
ip = stdin.readline
from collections import Counter
for _ in range(int(ip())):
	(n, k) = map(int, ip().split())
	s = set(list(map(int, ip().split())))
	i = 0
	while 1:
		if i not in s and k == 0:
			break
		elif i not in s and k > 0:
			k -= 1
		i += 1
	print(i)


import math
alf = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007

def createDic(nums):
	dic = dict()
	for i in nums:
		if not i in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	return dic

def subarray_sum_max(nums):
	array = []
	suma_parcial = 0
	max_sum = 0
	index = 0
	se_refresco = True
	for i in range(len(nums)):
		suma_parcial += nums[i]
		if max_sum < suma_parcial:
			if se_refresco:
				array = []
				se_refresco = False
				index = i
			max_sum = suma_parcial
		if suma_parcial < 0:
			suma_parcial = 0
			se_refresco = True
		elif not se_refresco:
			array.append(nums[i])
	return (array, index, max_sum)

def particiones(nums, index, array):
	if index == len(nums):
		count = 0
	else:
		for i in array:
			i.append(nums[index])
			particiones(nums, index + 1, array)
			i.pop(len(i) - 1)
		array.append([])
		array[len(array) - 1].append(nums[index])
		particiones(nums, index + 1, array)
		array.pop(len(array) - 1)

def busqueda_binaria(nums, x, a_insertar):
	izq = 0
	der = len(nums) - 1
	while izq <= der:
		medio = int((izq + der) / 2)
		if nums[medio] == x:
			return medio
		elif nums[medio] > x:
			der = medio - 1
		else:
			izq = medio + 1
	if a_insertar:
		nums.insert(medio + 1, x)
	return -1

def solve():
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	array = []
	for i in range(2 * 10 ** 5 + 1):
		array.append(False)
	for i in range(n):
		array[nums[i]] = True
	for i in range(len(array)):
		if k == 0:
			break
		if not array[i]:
			array[i] = True
			k -= 1
	for i in range(len(array)):
		if not array[i]:
			print(i)
			return
test = int(input())
while test != 0:
	solve()
	test -= 1


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m = max(a)
	c = [0] * (m + 2 + k)
	for i in a:
		c[i] = 1
	for i in range(len(c)):
		if k > 0 and c[i] == 0:
			c[i] = 1
			k -= 1
		if k == 0:
			break
	print(c.index(0))


tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	num_set = set(map(int, input().split()))
	num = 0
	while k >= 0:
		if num not in num_set:
			k -= 1
		num += 1
	print(num - 1)


T = int(input())
for x in range(T):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	t = [-1] * 200001
	for i in s:
		t[i] = i
	for i in range(200001):
		if t[i] == -1:
			k -= 1
		if k < 0:
			break
	print(i)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split(' ')]
	arr = [int(x) for x in input().split(' ')]
	temp = [-1] * 200001
	for i in arr:
		temp[i] = i
	for i in range(200001):
		if temp[i] == -1:
			k -= 1
		if k < 0:
			break
	print(i)


for _ in range(int(input())):
	(l, k) = map(int, input().split())
	s1 = set(list(map(int, input().split())))
	s2 = set(list((i for i in range(l + k + 1))))
	s3 = s1.symmetric_difference(s2)
	print(list(s3)[k])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = set(map(int, input().split()))
	t = 0
	mi = 0
	while t != k + 1:
		if mi in li:
			mi += 1
		else:
			ans = mi
			t += 1
			mi += 1
	print(ans)


def getRslt(st: set, lst: int, lAd: int):
	i = 0
	hld = lst + lAd
	while lAd != 0:
		if i not in st:
			st.add(i)
			lAd -= 1
		i += 1
	for i in range(0, hld):
		if i not in st:
			return i
	return i + 1
T = int(input())
while T != 0:
	(setCnt, addCnt) = [int(x) for x in input().split()]
	toAdd = [int(x) for x in input().split()]
	toAdd = sorted(toAdd)
	elem = set()
	for i in range(setCnt):
		elem.add(toAdd[i])
	print(getRslt(elem, setCnt, addCnt))
	T -= 1


for _ in range(int(input())):
	(n, b) = map(int, input().split())
	a = list(map(int, input().split()))
	a = set(a)
	c = 0
	while True:
		if c in a:
			c += 1
		elif b == 0:
			break
		else:
			c += 1
			b -= 1
	print(c)


from math import gcd, sqrt, ceil, floor, log10
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))

def inp_graph(n, adj, gtype=0):
	pass

def solve(*args, **kwargs):
	(n, k, arr) = args
	i = res = 0
	while True:
		if i not in arr:
			if k:
				k -= 1
			else:
				return i
		i += 1

def main(*args, **kwargs):
	for _ in range(int(input())):
		(arg1, arg2) = inp_vars(int, SPACE)
		arg3 = inp_vars(int, SPACE, set)
		res = solve(*(arg1, arg2, arg3))
		if type(res) in {list, tuple, set}:
			print(*res, sep=' ')
		else:
			print(res)
main()


t = int(input())
for i in range(t):
	(length, k) = map(int, input().split())
	s1 = set(list(map(int, input().split())))
	s2 = set([i for i in range(length + k + 1)])
	s3 = s1.symmetric_difference(s2)
	print(list(s3)[k])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	s = set(lst)
	i = 0
	while True:
		if i in s:
			i += 1
		elif k > 0:
			k -= 1
			i += 1
		else:
			break
	print(i)


for _ in range(int(input())):
	k = int(input().split()[-1])
	values = set(map(int, input().split()))
	value = 0
	while True:
		if value in values:
			value += 1
		elif k > 0:
			(k, value) = (k - 1, value + 1)
		else:
			print(value)
			break


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = set(map(int, input().split()))
	for i in range(0, 2 * 10 ** 5 + 1):
		if i not in s:
			if k != 0:
				k -= 1
			elif k == 0:
				print(i)
				break


def sol(n, k, l):
	s = set(l)
	i = 0
	while 1:
		if i in s:
			i += 1
		elif k > 0:
			k -= 1
			i += 1
		else:
			return i
for tc in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	print(sol(n, k, l))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = set(a)
	i = 0
	while True:
		if i in s:
			i += 1
		elif k > 0:
			k -= 1
			i += 1
		else:
			break
	print(i)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	li = set(li)
	for i in range(len(li) + 1 + k):
		if i in li:
			pass
		elif k != 0:
			k -= 1
		else:
			print(i)
			break
	if k != 0:
		print(i + k)


t = int(input())
ans = []
for i in range(t):
	gg = {}
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	for i in s:
		gg[i] = gg.get(i, 0) + 1
	j = 0
	while k != 0:
		if j not in gg:
			k -= 1
			gg[j] = gg.get(j, 0) + 1
		j += 1
	f = 0
	while True:
		if f not in gg:
			print(f)
			break
		f += 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	mx = max(l)
	l = set(l)
	con = False
	for i in range(mx):
		if k != 0:
			if i not in l:
				k -= 1
		elif i not in l:
			print(i)
			con = True
			break
	if k != 0:
		print(mx + k + 1)
	if k == 0 and con == False:
		print(mx + 1)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = sorted(map(int, input().split()))
	if len(list(set(range(0, s[-1])) - set(s))) > k:
		print(list(set(range(0, s[-1])) - set(s))[k])
	else:
		print(s[-1] + 1 + (k - len(list(set(range(0, s[-1])) - set(s)))))


t = int(input())
for x in range(t):
	(n, k) = [int(d) for d in input().split()]
	a = [int(d) for d in input().split()]
	s = set(a)
	mex = 0
	while True:
		if mex in s:
			mex += 1
		elif k > 0:
			k -= 1
			mex += 1
		else:
			break
	print(mex)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		d[i] = True
	(m, c) = (0, 0)
	while c <= k:
		if m not in d:
			d[m] = True
			c += 1
			if c > k:
				break
		m += 1
	print(m)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = set(list(map(int, input().split())))
	mex = 0
	while True:
		if mex in st:
			mex += 1
		elif k > 0:
			k -= 1
			mex += 1
		else:
			break
	print(mex)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = set(map(int, input().split()))
	m = max(l)
	p = set(range(m + 1))
	p = list(set(p) - l)
	if k < len(p):
		print(p[k])
	elif k == len(p):
		print(m + 1)
	else:
		print(m + k + 1)


t = int(input())
while t:
	(n, k) = map(int, input().split(' '))
	a = set(map(int, input().split(' ')))
	cnt = 0
	flag = True
	while flag:
		if cnt in a:
			cnt += 1
		elif k > 0:
			cnt += 1
			k -= 1
		else:
			print(cnt)
			flag = False
	t -= 1


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	S = set(list(map(int, input().split())))
	mex = 0
	while True:
		if mex in S:
			mex = mex + 1
		elif K > 0:
			K = K - 1
			mex = mex + 1
		else:
			break
	print(mex)


t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	arr = set(list(map(int, input().split())))
	mex = 0
	while True:
		if mex in arr:
			mex += 1
		elif k > 0:
			k -= 1
			mex += 1
		else:
			break
	print(mex)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = set(map(int, input().split()))
	i = 0
	while k >= 0:
		if i not in s:
			if k == 0:
				print(i)
				break
			else:
				s.add(i)
				k -= 1
		i += 1


t = int(input())
while t:
	(n, k) = map(int, input().split())
	unique = set()
	s = list(map(int, input().split()))
	for i in range(n):
		unique.add(s[i])
	i = 0
	while k >= 0:
		if k == 0:
			if i not in unique:
				print(i)
				break
			i = i + 1
		else:
			if i not in unique:
				k = k - 1
			i += 1
	t = t - 1


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	m = max(l)
	a = [0] * (m + 1)
	for i in range(n):
		a[l[i]] += 1
	x = a.count(0)
	if x > k:
		i = 0
		k += 1
		while k > 0:
			if a[i] == 0:
				k -= 1
			i += 1
		print(i - 1)
	else:
		k -= x
		print(m + k + 1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = set(map(int, input().split()))
	mex = 0
	while True:
		if mex in s:
			mex += 1
		elif k > 0:
			mex += 1
			k -= 1
		else:
			break
	print(mex)


def mex(nList):
	nList = set(nList)
	mex = 0
	while mex in nList:
		mex += 1
	return mex
for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = set(map(int, input().split()))
	mex = 0
	while True:
		if mex in arr:
			mex += 1
		elif k > 0:
			mex += 1
			k -= 1
		else:
			break
	print(mex)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = set(list(map(int, input().split())))
	z = 0
	while k != 0:
		if z not in l:
			l.add(z)
			z += 1
			k -= 1
		else:
			z += 1
	l = list(l)
	l.sort()
	if len(l) - 1 == l[-1]:
		print(l[-1] + 1)
	else:
		for i in range(0, l[-1]):
			if i != l[i]:
				print(i)
				break


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = [int(x) for x in input().split()]
	a = [0] * (max(s) + 1)
	for i in s:
		a[i] += 1
	k1 = 0
	for j in range(len(a)):
		if a[j] == 0:
			k1 += 1
			if k1 > k:
				print(j)
				break
	if k1 <= k:
		print(len(a) + k - k1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	l = list(set(arr))
	l.sort()
	if len(l) == 1:
		if k < l[0]:
			print(k)
		else:
			k = k - l[0]
			print(k + l[0] + 1)
	elif k < l[0]:
		print(k)
	else:
		flag = True
		k = k - l[0]
		for i in range(1, len(l)):
			diff = l[i] - l[i - 1] - 1
			if k < diff:
				print(l[i - 1] + k + 1)
				flag = False
				break
			elif k >= diff:
				k = k - diff
		if flag:
			print(l[-1] + k + 1)


def ayush(N, K, arr):
	no = k
	h = 0
	for j in range(N + K + 1):
		if j not in arr:
			if K > 0:
				K -= 1
			else:
				print(j)
				break
t = int(input())
for i in range(t):
	arr1 = input().split()
	n = int(arr1[0])
	k = int(arr1[1])
	arr2 = set(list(map(int, input().split())))
	ayush(n, k, arr2)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	flag = 0
	s = [int(i) for i in input().split()]
	ref = [0] * (n + k)
	for i in range(len(s)):
		if s[i] < n + k:
			ref[s[i]] = 1
	i = 0
	count = k
	while count:
		if ref[i] == 0:
			ref[i] = 1
			count -= 1
		i += 1
	for i in range(len(ref)):
		if ref[i] == 0:
			print(i)
			flag = 1
			break
	if flag == 0:
		print(n + k)
	t -= 1


def main():
	t = int(input())
	for t in range(t):
		(n, k) = map(int, input().split(' '))
		numbers = sorted(set(map(int, input().split(' '))))
		mex = 0
		for number in numbers:
			while k > 0 and number > mex:
				mex += 1
				k -= 1
			if number > mex:
				print(mex)
				break
			mex += 1
		else:
			print(mex + k)
main()


n = int(input())
for i in range(n):
	(n, k) = map(int, input().split())
	a = set(list(map(int, input().split())))
	n = n + k + 1
	escp = []
	for l in range(n):
		if l not in a:
			escp.append(l)
	print(escp[k])


def mex(set_size, add_num, d):
	max_num = max(d.keys())
	for i in range(0, max_num + add_num + 1):
		if i not in d:
			if add_num == 0:
				return i
			else:
				d[i] = 1
				add_num -= 1
	return max(d.keys()) + 1
n = int(input())
for i in range(n):
	(set_size, add_num) = [int(i) for i in input().split()]
	set_ = [int(i) for i in input().split()]
	d = {}
	for i in set_:
		d[i] = 1
	print(mex(set_size, add_num, d))


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	s = set(list(map(int, input().split())))
	m = 0
	while True:
		if m in s:
			m = m + 1
		elif k > 0:
			k = k - 1
			m = m + 1
		else:
			break
	print(m)
	t = t - 1


t = int(input())
while t:
	(n, k) = input().split()
	k = int(k)
	n = int(n)
	l = set(list(map(int, input().split())))
	for i in range(n + k + 1):
		if i not in l:
			if k > 0:
				k -= 1
			else:
				print(i)
				break
	t -= 1


for i in range(int(input())):
	(N, K) = map(int, input().split())
	multiset = set(list(map(int, input().split())))
	for j in range(N + K + 1):
		if j not in multiset:
			if K > 0:
				K -= 1
			else:
				print(j)
				break


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	nums = set(list(map(int, input().split())))
	m = 0
	while True:
		if m in nums:
			m += 1
		elif k > 0:
			k -= 1
			m += 1
		else:
			break
	print(m)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	h = max(arr)
	temp = [True] * (h + 1)
	for i in range(n):
		temp[arr[i]] = False
	temp1 = []
	for i in range(len(temp)):
		if temp[i]:
			temp1.append(i)
	if len(temp1) <= k:
		print(h + k - len(temp1) + 1)
	else:
		print(temp1[k])


j = int(input())
for i in range(j):
	(n, k) = map(int, input().split())
	s = set(list(map(int, input().split())))
	c = 0
	while True:
		if c in s:
			c += 1
		elif k > 0:
			k -= 1
			c += 1
		else:
			break
	print(c)


a = int(input())
for i in range(a):
	(r, k) = map(int, input().split())
	x = set(list(map(int, input().split())))
	a = 0
	while True:
		if a in x:
			a += 1
		elif k > 0:
			k -= 1
			a += 1
		else:
			break
	print(a)


t = int(input())
while t != 0:
	(n, x) = map(int, input().split(' '))
	arr = set(list(map(int, input().split(' '))))
	m = 0
	while True:
		if m in arr:
			m += 1
		elif x > 0:
			m += 1
			x -= 1
		else:
			break
	print(m)
	t -= 1