God's Blessing on This PermutationForces!

A Random Pebble

You are given a permutation $p_1,p_2,\ldots,p_n$ of length $n$ and a positive integer $k \le n$.

In one operation you can choose two indices $i$ and $j$ ($1 \le i < j \le n$) and swap $p_i$ with $p_j$.

Find the minimum number of operations needed to make the sum $p_1 + p_2 + \ldots + p_k$ as small as possible.

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 100$).

The second line of each test case contains $n$ integers $p_1,p_2,\ldots,p_n$ ($1 \le p_i \le n$). It is guaranteed that the given numbers form a permutation of length $n$.


-----Output-----

For each test case print one integer — the minimum number of operations needed to make the sum $p_1 + p_2 + \ldots + p_k$ as small as possible.


-----Examples-----

Input
4
3 1
2 3 1
3 3
1 2 3
4 2
3 4 1 2
1 1
1
Output
1
0
2
0


-----Note-----

In the first test case, the value of $p_1 + p_2 + \ldots + p_k$ is initially equal to $2$, but the smallest possible value is $1$. You can achieve it by swapping $p_1$ with $p_3$, resulting in the permutation $[1, 3, 2]$.

In the second test case, the sum is already as small as possible, so the answer is $0$.

Difficulty: EASY
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for i in range(int(input())):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	if k == n:
		print('0')
	else:
		lis1 = lis.copy()
		lis1.sort()
		lisans1 = lis1[:k]
		lisans = lis[:k]
		count = 0
		for j in range(len(lisans1)):
			if lisans1[j] not in lisans:
				count += 1
		print(count)


import sys
input = lambda : sys.stdin.readline().rstrip()

def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	b = list(sorted(arr))
	a = arr[:k]
	b = b[:k]
	a.sort()
	for x in a:
		if x not in b:
			ans += 1
		else:
			b.remove(x)
	return ans
for __ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	print(sum((a[i] > k for i in range(k))))


import sys
inf = float('inf')
mod = 10 ** 5 + 7
input = lambda : sys.stdin.readline().rstrip()
inpnm = lambda : map(int, input().split())
inparr = lambda : [int(i) for i in input().split()]
inpint = lambda : int(input())
for case in range(inpint()):
	(n, k) = inpnm()
	arr = inparr()
	res = 0
	t = set(arr[:k])
	for i in range(1, k + 1):
		if i not in t:
			res += 1
	print(res)


import sys
input = sys.stdin.readline

def int_num():
	return int(input())

def int_list():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	(n, k) = int_list()
	lst = int_list()
	ans = 0
	for i in range(k):
		if lst[i] > k:
			ans += 1
	print(ans)

def main():
	test_case = int_num()
	while test_case:
		solve()
		test_case -= 1
	return
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {}
	for i in range(k):
		d[a[i]] = 1
	ans = 0
	for i in range(1, k + 1):
		if i not in d:
			ans += 1
	print(ans)


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


def sol():
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	counter = 0
	for i in range(k, n):
		if p[i] <= k:
			counter += 1
	print(counter)
for _ in range(int(input())):
	sol()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = l.copy()
	l1.sort()
	ans = 0
	for i in l[0:k]:
		if i not in l1[0:k]:
			ans += 1
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	data = list(map(int, input().split()))
	count = 0
	for num in data[:k]:
		if num > k:
			count += 1
	print(count)


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


rez_mass = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	array = list(map(int, input().split()))
	result = 0
	for i in range(k):
		if array[i] > k:
			result += 1
	rez_mass.append(result)
print(*rez_mass, sep='\n')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	sp = list(map(int, input().split()))
	print(len(set(sorted(sp)[:k]).difference(set(sp[:k]))))


import math
import collections
import itertools
import functools

def fun(t):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	a = set()
	b = set()
	for i in range(k):
		a.add(arr[i])
		b.add(i + 1)
	print(k - len(a & b))
for tc in range(int(input())):
	fun(tc)


t = int(input())
for case in range(t):
	ipt1 = input().split(' ')
	n = int(ipt1[0])
	k = int(ipt1[1])
	arr = [int(x) for x in input().split(' ')]
	count = 0
	for i in range(0, k):
		if arr[i] > k:
			count += 1
	print(count)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	k1 = k
	itog = a[:k]
	for i in range(1, k + 1):
		if i in itog:
			k1 -= 1
	print(k1)


from heapq import *
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	pq = arr.copy()
	heapify(pq)
	ans = 0
	s = set()
	for i in range(k):
		s.add(heappop(pq))
	for i in range(k):
		if arr[i] not in s:
			ans += 1
	print(ans)


t = int(input())
O = [0] * t
for ii in range(t):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	for i in p[:k]:
		if i > k:
			O[ii] += 1
for i in range(t):
	print(O[i])


for i in range(int(input())):
	(x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	c = y
	for i in range(y):
		if l[i] <= y:
			c -= 1
	print(c)


for __ in range(int(input())):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	swap = k
	for i in range(k):
		if lis[i] <= k:
			swap -= 1
	print(swap)


T = int(input())
ans = []
for tc in range(T):
	(n, k) = map(int, input().split(' '))
	p = list(map(int, input().split(' ')))
	if n == k:
		ans.append(0)
	else:
		temp = 0
		for i in range(k, n):
			if p[i] <= k:
				temp = temp + 1
		ans.append(temp)
for i in ans:
	print(i)


def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = inp()
for i in range(t):
	nk = inlt()
	n = nk[0]
	k = nk[1]
	counter = 0
	arr = inlt()
	for j in range(k):
		if arr[j] > k:
			counter = counter + 1
	print(counter)


def swap(a, b):
	return len(a) - len([v for v in a if v in b])
n_t = int(input())
for _ in range(n_t):
	(n, k) = [int(i) for i in input().split(' ')]
	l = [int(i) for i in input().split(' ')]
	l_min = l.copy()
	l_min.sort()
	print(swap(l[:k], l_min[:k]))


t = int(input())
for te in range(t):
	temp = input().split(' ')
	(n, k) = (int(temp[0]), int(temp[1]))
	temp = input().split(' ')
	arr = []
	for i in range(0, n):
		arr.append(int(temp[i]))
	ans = 0
	for i in range(k):
		if arr[i] > k:
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = a.copy()
	b.sort()
	cnt = 0
	for i in range(k):
		if a.index(b[i]) >= k:
			cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	L = list(map(int, input().split()))
	i = k - 1
	c = 0
	while i >= 0:
		if L[i] > k:
			c += 1
			i -= 1
		else:
			i -= 1
	print(c)


import math

def slave():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	for i in range(k):
		if a[i] > k:
			s += 1
	print(s)
t = int(input())
for i in range(t):
	slave()


T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	listA = list(map(int, input().split()))
	anuvab = []
	for j in range(len(listA)):
		anuvab.append(listA[j])
	anuvab.sort()
	for i in range(len(listA) - 1, k - 1, -1):
		anuvab.remove(anuvab[i])
	if n == k:
		print(0)
	elif n > k:
		count = 0
		for i in range(k):
			if listA[i] in anuvab:
				count = count
			else:
				count = count + 1
		print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	count = 0
	if k == n:
		ans = 0
	else:
		brr = sorted(arr)
		for i in range(k):
			if brr[i] not in arr[:k]:
				count += 1
			else:
				continue
	print(count)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr1 = arr[k:]
	i = k - 1
	j = 0
	arr1.sort()
	arr2 = arr[0:k]
	arr2.sort()
	count = 0
	while i >= 0 and j <= n - 1 - k and (arr2[i] > arr1[j]):
		count += 1
		j += 1
		i -= 1
	print(count)


def solve(arr, n, k):
	c = 0
	for i in arr[:k]:
		if i > k:
			c += 1
	return c
t = int(input())
res = []
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	res.append(solve(arr, n, k))
for ele in res:
	print(ele)


import sys
input = sys.stdin.readline
T = int(input())
while T:
	(n, k) = map(int, input().split())
	pool = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		if pool[i] > k:
			ans += 1
	print(ans)
	T -= 1


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	lis = sorted(a)[:k]
	a = a[:k]
	cnt = 0
	for i in lis:
		if i not in a:
			cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	List = list(map(int, input().split()))
	first = List[k:]
	second = [i for i in range(k + 1, n + 1)]
	s1 = set(first)
	s2 = set(second)
	a = len(s1 & s2)
	print(n - k - a)


def z(t):
	for j in range(t):
		v = 0
		(n, k) = map(int, input().split())
		P = list(map(int, input().split()))
		for i in range(k):
			if P[i] > k:
				v += 1
		print(v)
T = int(input())
z(T)


t = int(input())
s = 0
while t > 0:
	(n, k) = [int(i) for i in input().split()]
	p = [int(i) for i in input().split()]
	l = p
	l = sorted(l)
	for i in range(k):
		if p.index(l[i]) >= k:
			s += 1
	print(s)
	t -= 1
	s = 0


for i in range(int(input())):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	arr = [0] * k
	c = 0
	for j in range(0, k):
		arr[c] = p[j]
		c += 1
	swap = 0
	p.sort()
	for j in range(k):
		if p[j] not in arr:
			swap += 1
	print(swap)


n = int(input())
res = []
for i in range(n):
	count = 0
	lenk = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	for k in range(lenk[1], lenk[0]):
		if arr[k] <= lenk[1]:
			count += 1
	res.append(count)
list(map(print, res))


T = int(input())
q = []
for i in range(T):
	x = input().split()
	(n, k) = (int(x[0]), int(x[1]))
	data = [int(i) for i in input().split()]
	q.append((n, k, data))

def solve(n, k, data):
	datas = sorted(data)
	cur_data = data[:k]
	for d in datas[:k]:
		if d in cur_data:
			cur_data.remove(d)
	print(len(cur_data))
for (n, k, data) in q:
	solve(n, k, data)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	p = set(arr[:k])
	arr.sort()
	P = set(arr[:k])
	print(len(P.difference(p)))


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


for ii in range(int(input())):
	(a, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	s = 0
	for i in arr[:k]:
		if i > k:
			s += 1
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	count = 0
	for i in range(k):
		if l[i] > k:
			count += 1
	print(count)


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a1 = a[0:k]
	a.sort()
	a2 = a[0:k]
	cnt = 0
	for i in a1:
		if i not in a2:
			cnt = cnt + 1
	print(cnt)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	x = l[:b]
	c = 0
	y = sorted(l)
	for i in range(b):
		try:
			n = x.index(y[i])
		except:
			c += 1
	print(c)


t = int(input())
for test in range(t):
	(n, k) = map(int, input().split())
	cnt = 0
	p = list(map(int, input().split()))
	for i in range(k):
		if p[i] > k:
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	for x in [*map(int, input().split())][:k]:
		if x > k:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	p1 = [int(i) for i in input().split()]
	p2 = set(sorted(p1)[:k])
	ans = 0
	for i in range(k):
		if p1[i] in p2:
			p2.remove(p1[i])
		else:
			ans += 1
	print(ans)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	b = []
	for i in range(k):
		b.append(a[i])
	for j in range(k):
		if j + 1 not in b:
			count = count + 1
	print(count)
	t = t - 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mass = list(map(int, input().split()))
	otv = 0
	for i in range(k):
		if mass[i] > k:
			otv += 1
	print(otv)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	pos = [0 for _ in range(0, n + 1)]
	for _ in range(0, n):
		pos[a[_]] = _
	answer = 0
	for num in range(1, k + 1):
		if pos[num] >= k:
			answer += 1
	print(answer)


a = int(input())
for y in range(a):
	(b, c) = map(int, input().split())
	d = list(map(int, input().split()))
	j = d[:c]
	j.sort()
	s = 0
	for y in range(c):
		if j[y] > c:
			s += 1
	print(s)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	nums = list(map(int, input().split(' ')))
	ans = 0
	for i in range(k):
		if nums[i] > k:
			ans += 1
	print(ans)


res = []
for _ in range(int(input())):
	tmp = 0
	(n, k) = map(int, input().split())
	if n == k:
		res.append(0)
		input()
		continue
	arrn = list(map(int, input().split()))
	if sum(arrn) != (1 + n) / 2 * n:
		res.append(0)
		continue
	arrk = [i for i in range(1, k + 1)]
	for i in arrk:
		if not i in arrn[:k]:
			tmp += 1
	res.append(tmp)
for i in res:
	print(i)


t = int(input())
i = 0
juturlist = []
while i < t:
	s = input()
	iterlist = s.split()
	u = input()
	iterlist_answer = u.split()
	j = 0
	puturlist = []
	while j < int(iterlist[1]):
		puturlist.append(j + 1)
		j += 1
	k = 0
	count = 0
	while k < int(iterlist[1]):
		if int(iterlist_answer[k]) in puturlist:
			k += 1
		else:
			count += 1
			k += 1
	juturlist.append(count)
	i += 1
m = 0
while m < len(juturlist):
	print(juturlist[m])
	m += 1


test_num = int(input())
for i in range(test_num):
	(nr, kr) = input().split()
	(n, k) = (int(nr), int(kr))
	numberr = input().split()
	number = [int(e) for e in numberr]
	opr = 0
	for p in number[:k]:
		if p > k:
			opr = opr + 1
	print(opr)


for _ in ' ' * int(input()):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	if n == k:
		print(0)
	else:
		a = set(x[:k])
		b = set(range(1, k + 1))
		if a == b:
			print(0)
		else:
			s = b.difference(a)
			print(len(s))


t = int(input())
res = []
for i in range(t):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	tab = input().split(' ')
	if (n == 1) | (k == n):
		res.append(0)
	else:
		summ = 0
		for j in range(k):
			if int(tab[j]) > k:
				summ += 1
		res.append(summ)
for i in res:
	print(i)


t = int(input())
for _ in range(t):
	[n, k] = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	s = 0
	for x in a[:k]:
		if x > k:
			s += 1
	print(s)


def solve(n, k, arr):
	moves = 0
	for i in range(k, n):
		if arr[i] <= k:
			moves += 1
	return moves
t = int(input())
for _ in range(0, t):
	[n, k] = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	print(solve(n, k, arr))


def min_permutation(left_mass, right_mass):
	n = min(len(left_mass), len(right_mass))
	counter = 0
	while counter != n and left_mass[counter] - right_mass[counter] > 0:
		counter += 1
	return counter
t = int(input())
array = []
for i in range(t):
	(n, k) = map(int, input().split())
	m = [int(x) for x in input().split()]
	(left_mass, right_mass) = ([], [])
	for j in range(n):
		if j <= k - 1:
			left_mass.append(m[j])
		else:
			right_mass.append(m[j])
	left_mass.sort(reverse=True)
	right_mass.sort()
	array.append(min_permutation(left_mass, right_mass))
for i in range(len(array)):
	print(array[i])


from sys import stdin
rd = stdin.readline
for _ in range(int(rd())):
	(n, k) = map(int, rd().split())
	p = list(map(int, rd().split()))
	print(sum((p[i] > k for i in range(k))))


t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	s = [int(x) for x in input().split()]
	c = s.copy()
	c.sort()
	count = 0
	for g in s[0:k]:
		if g in c[0:k]:
			continue
		else:
			count += 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ct = 0
	d = {}
	for i in range(1, k + 1):
		d[i] = l.index(i)
	for i in d:
		if d[i] >= k:
			ct += 1
	print(ct)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	h = l.copy()
	h.sort()
	mink = h[:k]
	if h == l:
		print(0)
	else:
		pp = k
		for j in range(k):
			if l[j] in mink:
				pp -= 1
		print(pp)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	array = list(map(int, input().split(' ')))
	print(k - sum([i <= k for i in array[:k]]))


import sys
input = sys.stdin.readline
M = int(1000000000.0) + 7

def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		ans += a[i] > k
	return ans
for _ in range(int(input())):
	print(solve())


def solve():
	(n, k) = map(int, input().split())
	al = list(map(int, input().split()))
	cnt = 0
	for i in range(k):
		if al[i] > k:
			cnt += 1
	print(cnt)
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	a = 0
	for i in range(n - k):
		l.pop()
	for i in range(1, k + 1):
		if i in l:
			a = a + 1
	print(k - a)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = set(l[:k])
	l2 = set(sorted(l)[:k])
	s = l1 - l2
	print(len(s))


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	bad = 0
	for i in range(k):
		if arr[i] > k:
			bad += 1
	print(bad)


for _ in range(int(input())):
	(n, k) = [int(_) for _ in input().split()]
	X = set([int(_) for _ in input().split()][:k])
	U = set([_ + 1 for _ in range(k)])
	print(len(X - U))


for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	li = [int(j) for j in input().split()]
	out = 0
	for p in li[0:k]:
		if p > k:
			out = out + 1
	print(out)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	x = x[0:b]
	count = 0
	for i in range(1, b + 1):
		if i not in x:
			count += 1
	print(count)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		if lst[i] > k:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for i in range(k):
		if l[i] <= k:
			pass
		else:
			c += 1
	if c == k:
		print(c)
	else:
		print(c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	res = 0
	for i in range(k):
		if arr[i] > k:
			res += 1
	print(res)


t = int(input())
for _ in range(t):
	(n, k) = (int(i) for i in input().split())
	p = [int(i) for i in input().split()]
	res = len(set(p[:k]) - set(sorted(p)[:k]))
	print(res)


t = int(input())
ans = []
for _ in range(t):
	(n, k) = map(int, input().split())
	ans += [sum([1 if c > k else 0 for c in list(map(int, input().split()))[:k]])]
print(*ans, sep='\n')


for x in range(int(input())):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()[:n]))
	counter = 0
	if n != k:
		for i in range(1, k + 1):
			if i not in p[0:k]:
				counter += 1
	print(counter)


for a in range(int(input())):
	(b, c) = map(int, input().split())
	e = 0
	d = list(map(int, input().split()))
	for _ in range(c):
		if d[_] > c:
			e += 1
	print(e)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	z = sorted(a)
	x = 0
	for i in range(k):
		if z[i] not in a[:k]:
			x += 1
	print(x)


t = int(input())
for _ in range(t):
	inp1 = list(map(int, input().split()))
	n = inp1[0]
	k = inp1[1]
	inp2 = list(map(int, input().split()))
	if k == n:
		print(0)
		continue
	ans = 0
	for i in range(1, k + 1):
		if i in inp2[:k]:
			pass
		else:
			ans += 1
	print(ans)


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


test = int(input())
while test:
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	c = 0
	for i in range(k):
		if a[i] > k:
			c += 1
	print(c)
	test -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	p = [int(i) for i in input().split()]
	count = 0
	for i in range(1, k + 1):
		if i in p[:k]:
			pass
		else:
			count += 1
	print(count)


for i in range(int(input())):
	inp = list(map(int, input().split()))
	k = inp[1]
	array = list(map(int, input().split()))
	reqd = []
	for i in range(1, k + 1):
		reqd.append(i)
	ans = 0
	array = array[0:k]
	for x in array:
		if x not in reqd:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = map(int, input().split())
	A = list(A)
	c = 0
	if k == len(A):
		c = 0
	else:
		for i in range(k, len(A)):
			if A[i] <= k:
				c += 1
	print(c)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	res = k
	els = []
	for i in range(k):
		els.append(arr[i])
	arr.sort()
	for i in range(k):
		if arr[i] in els:
			res -= 1
	print(res)


t = int(input())
for i in range(0, t):
	(n, k) = (int(x) for x in input().split())
	L = [int(x) for x in input().split()]
	C = L[k:n]
	L.sort()
	L = L[k:n]
	a = len(C)
	count = 0
	for i in range(0, a):
		if C[i] not in L:
			count += 1
	print(count)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(sum((a[i] > k for i in range(k))))
	t -= 1