Read problems statements [Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

You are given an integer sequence $A$ with length $N$. In one move, you are allowed to choose one element of this sequence and change it to an arbitrary integer. Compute the minimum number of moves needed to make the sequence a permutation of the integers $1$ through $N$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the minimum required number of moves.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
the sum of $N$ for all test cases does not exceed $2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$ for each valid $i$

----- Sample Input 1 ------ 
2

4

1 2 3 3

3

2 6 2
----- Sample Output 1 ------ 
1

2
----- explanation 1 ------ 
Example case 1: One possible way is to change the last element to $4$. This creates the sequence $1, 2, 3, 4$, which is a permutation.

Example case 2: We can change the first element to $1$ and the second element to $3$, creating the permutation $1, 3, 2$.

Source: codechef | Difficulty: EASY
Tags: Data structures

Implementation


Solutions:
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	count = 0
	for j in s:
		if j <= n:
			count += 1
	ans = len(a) - count
	print(ans)


for i in range(int(input())):
	n = int(input())
	c = 0
	S = {int(i) for i in input().split()}
	for i in range(1, n + 1):
		if i not in S:
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	c = 0
	A = list(map(int, input().split()))
	S = set(A)
	for i in range(1, n + 1):
		if i not in S:
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	s = set(a)
	for i in range(1, n + 1):
		if i not in s:
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = set([int(x) for x in input().split()])
	ans = 0
	for i in range(1, n + 1):
		if i not in a:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	c = 0
	for (i, j) in d.items():
		if j > 1 and i <= n:
			c += j - 1
		if i > n:
			c += j
	print(c)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	c = 0
	for (k, v) in d.items():
		if k > n:
			c += v
		if k <= n and v > 1:
			c += v - 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mp = {}
	for i in a:
		if i >= 1 and i <= n and (i not in mp):
			mp[i] = 1
	print(n - len(mp))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dic = {}
	for i in l:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	c = 0
	for (a, b) in dic.items():
		if b > 1:
			c += b - 1
		if a > n:
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dic = {}
	for i in l:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	c = 0
	for (i, j) in dic.items():
		if j > 1:
			c += j - 1
		if i > n:
			c += 1
	print(c)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	ideal = list()
	for a in A:
		if a <= N:
			ideal.append(a)
	print(N - len(set(ideal)))


T = int(input())
for i in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	dic = {}
	for i in arr:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	cnt = 0
	for (i, j) in dic.items():
		if j > 1:
			cnt += j - 1
		if i > n:
			cnt += 1
	print(cnt)


for i in range(int(input())):
	kavya = int(input())
	loves = list(map(int, input().split()))
	sri = set(loves)
	counting = 0
	for i in range(1, kavya + 1):
		if i in sri:
			continue
		else:
			counting += 1
	print(counting)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	c = 0
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for i in range(1, n + 1):
		if i not in d:
			c += 1
		else:
			continue
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	s = set(l)
	ans = n - len(s)
	for i in s:
		if i > n or i < 0:
			ans += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	lst = set(list(map(lambda x: int(x), input().split(' '))))
	count = 0
	for i in range(1, n + 1):
		if i not in lst:
			count += 1
	print(count)


import collections
tt = int(input())
for i in range(tt):
	n = int(input())
	lst = list(map(int, input().split()))
	s = set(range(1, n + 1)).difference(set(lst))
	print(len(s))


for _ in range(int(input())):
	n = int(input())
	l = set(map(int, input().split()))
	count = 0
	for i in l:
		if i <= n:
			count += 1
	print(n - count)


testcase = int(input())
for i in range(testcase):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	c = set(l)
	for i in range(1, n + 1):
		if i not in c:
			count += 1
	print(count)


t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	d = {}
	for a in arr:
		if a in d:
			d[a] += 1
		else:
			d[a] = 1
	count = 0
	for key in d:
		if key > n:
			count += d[key]
		elif key <= n and d[key] > 1:
			count += d[key] - 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = set(l)
	ans = 0
	for i in range(1, n + 1):
		if i not in c:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	unique = sorted(list(set(arr)))
	count = 0
	for i in unique:
		if i > n:
			break
		else:
			count = count + 1
	print(n - count)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	l = n - len(b)
	count = 0
	for i in b:
		if i > n:
			count += 1
	print(count + l)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = {}
	for i in range(1, n + 1):
		f[i] = 0
	for i in a:
		if i in f:
			f[i] = 1
	c = 0
	for i in f.values():
		if i == 0:
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = set(map(int, input().split()))
	s = n - len(l)
	for i in l:
		if i <= n:
			pass
		else:
			s += 1
	print(s)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	l = []
	for i in a:
		if i <= n:
			l.append(i)
	l = set(l)
	print(n - len(l))


t = int(input())
for _ in range(t):
	ans = 0
	n = int(input())
	ar = list(map(int, input().split()))
	rep_store = set()
	for i in ar:
		if i > n:
			ans += 1
		elif i in rep_store:
			ans += 1
		else:
			rep_store.add(i)
	print(ans)


for i in range(int(input())):
	N = int(input())
	A = [int(k) for k in input().split()]
	l_st = []
	count = 0
	for i in range(N):
		if A[i] in l_st or A[i] > N:
			count += 1
		else:
			l_st.append(A[i])
	print(count)


T = int(input())
for _ in range(0, T):
	n = int(input())
	a = list(map(int, input().split()))
	b = [*set(a)]
	b = sorted(b)
	count = 0
	for i in range(0, len(b)):
		if b[i] <= n:
			count += 1
		else:
			break
	print(n - count)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = [i for i in x if i <= n]
	y = set(y)
	print(n - len(y))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	ct = 0
	for j in range(1, n + 1):
		if j not in s:
			ct += 1
	print(ct)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	cnt = 0
	s1 = set(lst)
	for i in range(1, n + 1):
		if i not in s1:
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	check = []
	l = list(map(int, input().split()))
	for i in l:
		if i <= n and i not in check:
			check.append(i)
	print(n - len(check))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = n - len(set(arr))
	s = set(arr)
	for i in s:
		if i < 1 or i > n:
			res += 1
	print(res)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	b = list(b)
	c = 0
	for i in range(len(b)):
		if b[i] <= n:
			c = c + 1
	print(n - c)
	t = t - 1


t = input()
for x in range(0, int(t)):
	c = 0
	n = int(input())
	e = [int(i) for i in input().split()][:n]
	k = set(e)
	for i in range(1, n + 1):
		if i not in k:
			c = c + 1
	print(c)


def permutation(arr, n):
	count = 0
	temp = set(arr)
	for i in range(1, n + 1):
		if i not in temp:
			count = count + 1
	print(count)
testcases = int(input())
for i in range(testcases):
	n = int(input())
	arr = list(map(int, input().split()))
	permutation(arr, n)


def permu(a, n):
	count = 0
	set1 = set(a)
	for i in range(1, n + 1):
		if i not in set1:
			count += 1
	print(count)
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	permu(a, n)


for x in range(int(input())):
	n = int(input())
	a = [int(d) for d in input().split()]
	final = []
	count = 0
	for i in a:
		if i not in final and i <= n:
			final.append(i)
		else:
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	temp = list(set(arr))
	ans = n - len(temp)
	for i in temp:
		if i > n:
			ans += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	a = set(a)
	b = set((x + 1 for x in range(n)))
	q = b.difference(a)
	print(len(q))


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	flag = 1
	for i in range(n):
		if arr[i] > n:
			arr[i] = 0
			flag = 0
	if flag == 1:
		print(n - len(set(arr)))
	else:
		print(n + 1 - len(set(arr)))


for _ in range(int(input().strip())):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	ans = n - len(set(a))
	set_a = set(a)
	for k in set_a:
		if k < 1 or k > n:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	count = 0
	listi = sorted(list(map(int, input().split())))
	for i in reversed(range(n)):
		if listi[i] > n:
			count = count + 1
		elif listi[i] <= n and listi[i] == listi[i - 1]:
			count = count + 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		if arr[i] not in d:
			d[arr[i]] = 1
		else:
			d[arr[i]] += 1
	change_req = 0
	for i in d:
		if i > n:
			change_req += d[i]
		elif d[i] > 1:
			change_req += d[i] - 1
	print(change_req)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = set()
	for i in a:
		if i <= n:
			s.add(i)
	print(n - len(s))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = []
	count = 0
	for i in a:
		if i not in s and i <= n:
			s.append(i)
		else:
			count += 1
	print(count)


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
import sys
import time
import string
sys.setrecursionlimit(3000000)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))

def solve(*args, **kwargs):
	(n, arr) = args
	hshst = set(arr)
	cnt = 0
	for num in range(1, n + 1):
		cnt += num not in hshst
	return cnt

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


for x in range(int(input())):
	n = int(input())
	a = [int(d) for d in input().split()]
	s = []
	for i in a:
		if i not in s and i <= n:
			s.append(i)
	print(n - len(s))


for x in range(int(input())):
	n = int(input())
	a = [int(d) for d in input().split()]
	s = {}
	for i in a:
		if i <= n:
			s[i] = i
	print(n - len(s))


tests = int(input())
for i in range(tests):
	length = int(input())
	input_set = set(map(int, input().split()))
	ans = 0
	for j in range(1, length + 1):
		if j not in input_set:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	for j in range(n):
		if a[j] > n:
			c += 1
		elif a[j] == a[j - 1]:
			c += 1
	print(c)


def f(n, arr):
	ans = 0
	lst = [0] * n
	for i in arr:
		if i <= n:
			lst[i - 1] = 1
	for i in lst:
		if i == 0:
			ans += 1
	return ans
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	ans = f(n, arr)
	print(ans)
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	rep = set()
	for j in l:
		if j > n:
			c += 1
		elif j in rep:
			c += 1
		else:
			rep.add(j)
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = set(map(int, input().split()))
	c = 0
	for i in range(1, n + 1):
		if i not in arr:
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = set(map(int, input().split()))
	k = 0
	for i in l:
		if i > n:
			k += 1
	print(n - len(l) + k)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = list(set(a))
	c = len(a) - len(d)
	for i in d:
		if i > n:
			c += 1
	print(c)


from collections import Counter
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	d = Counter(l)
	for i in d:
		if i > n:
			c = c + d[i]
		else:
			if d[i] > 1:
				c = c + (d[i] - 1)
			if d[i] < 1:
				c = c - 1
	print(c)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = Counter(a)
	ans = 0
	for i in d:
		if 1 <= i <= n:
			d[i] -= 1
			ans += d[i]
		else:
			ans += d[i]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = list(set(l))
	count = len(l) - len(d)
	for j in range(len(d)):
		if d[j] > n:
			count += 1
	print(count)