Alice and Bob are playing a game. They have an array of positive integers $a$ of size $n$.

Before starting the game, Alice chooses an integer $k \ge 0$. The game lasts for $k$ stages, the stages are numbered from $1$ to $k$. During the $i$-th stage, Alice must remove an element from the array that is less than or equal to $k - i + 1$. After that, if the array is not empty, Bob must add $k - i + 1$ to an arbitrary element of the array. Note that both Alice's move and Bob's move are two parts of the same stage of the game. If Alice can't delete an element during some stage, she loses. If the $k$-th stage ends and Alice hasn't lost yet, she wins.

Your task is to determine the maximum value of $k$ such that Alice can win if both players play optimally. Bob plays against Alice, so he tries to make her lose the game, if it's possible.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the size of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).


-----Output-----

For each test case, print one integer — the maximum value of $k$ such that Alice can win if both players play optimally.


-----Examples-----

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


-----Note-----

None

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Implementation

Greedy algorithms

Game theory

Data structures


Solutions:
n = int(input())
for i in range(n):
	s = int(input())
	r = [int(x) for x in input().split()]
	z = 0
	if 1 in r:
		r.pop(r.index(1))
		z += 1
	while 1 in r:
		r.pop(r.index(1))
		for j in range(z + 1, 0, -1):
			if j in r:
				r.pop(r.index(j))
				z += 1
				break
	print(z)


t = int(input())
for _ in range(t):
	n = int(input())
	lis = [int(x) for x in input().split(' ')]
	lis.sort()
	num = lis.count(1)
	s = min(num, n // 2 + n % 2)
	check = False
	for k in range(1, s + 1):
		lists = lis[k - 1:2 * k - 1]
		for i in range(k):
			if lists[i] > i + 1:
				check = True
				break
		if check:
			s = k - 1
			break
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	array = [int(x) for x in input().split()]
	k_max = array.count(1)
	if k_max == 0:
		print(0)
	else:
		kk = 0
		array = sorted(array)
		for k in range(1, min(k_max + 1, int((n + 3) / 2))):
			array_0 = array[k - 1:2 * k]
			if all([array_0[i] <= i + 1 for i in range(k)]):
				kk = k
		print(kk)


def cal(n, arr):
	if arr[0] != 1:
		return 0
	if n == 1:
		return 1
	t = arr.count(1)
	for i in range(t, -1, -1):
		if i + i - 1 > n:
			continue
		tag = 0
		for j in range(i - 1, 2 * i - 1):
			if arr[j] > j - i + 2:
				tag = 1
				break
		if tag == 0:
			return i
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr.sort()
	print(cal(n, arr))


t = int(input())
for v in range(t):
	m = int(input())
	j = input().split()
	h = [int(i) for i in j]
	h.sort()
	count = 0
	while True:
		val = 1
		check = 0
		temp = h[count:count * 2 + 1]
		if temp == [] or len(temp) != count + 1:
			break
		for k in temp:
			if k <= val:
				val += 1
			else:
				check = 1
				break
		if check == 0:
			count += 1
		else:
			break
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	if arr[0] != 1:
		print(0)
	elif n == 1:
		print(1)
	else:
		t = arr.count(1)
		for i in range(t, -1, -1):
			if i + i - 1 > n:
				continue
			tag = 0
			for j in range(i - 1, 2 * i - 1):
				if arr[j] > j - i + 2:
					tag = 1
					break
			if tag == 0:
				print(i)
				break


from itertools import count
from math import ceil
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = {}
	for i in a:
		f[i] = f.get(i, 0) + 1
	if f.get(1, 0) == 0:
		print(0)
	else:
		count1 = 0
		f[1] -= 1
		k = 1
		for j in range(2, ceil(n / 2) + 1):
			if f.get(j, -1) == -1:
				if count1 == 0:
					f[1] -= 2
				else:
					count1 -= 1
					f[1] -= 1
			else:
				count1 += f[j] - 1
				f[1] -= 1
			if f[1] < 0:
				break
			if count1 < 0:
				break
			k = j
		print(k)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = a.count(1)
	m = 1
	pos = 0
	a.sort()
	a.append(n + 1)
	(l, r) = (0, k + 1)
	while r - l > 1:
		flag = True
		M = (l + r) // 2
		for i in range(M - 1, M + M - 1):
			if a[i] > i - M + 2:
				flag = False
				break
		if flag:
			l = M
		else:
			r = M
	print(l)


for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	for k in range(n, -1, -1):
		if all((k - 1 + i < n and a[k - 1 + i] <= i + 1 for i in range(k))):
			print(k)
			break


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	maxx = 0
	k = 1
	while 2 * k - 2 < n:
		i = 2 * k - 2
		j = k
		while j >= 1:
			if a[i] > j:
				break
			i -= 1
			j -= 1
		if j == 0:
			maxx = k
		else:
			break
		k += 1
	print(maxx)


z = int(input())
for i in range(z):
	integer_number = int(input())
	num_array = sorted(list(map(int, input().split())))
	num_of_1 = 0
	for j in num_array:
		if j == 1:
			num_of_1 += 1
		else:
			break
	current_max = num_of_1
	k = num_of_1
	l = 2
	while k <= 2 * current_max - 2:
		try:
			if num_array[k] <= l:
				k += 1
				l += 1
			else:
				current_max -= 1
				l += 1
		except:
			current_max -= 1
			l += 1
	print(current_max)


def f(kk):
	ff = True
	for j in range(kk + 1):
		if c[j] <= kk + j:
			ff = False
			break
	return ff
t = int(input())
for ii in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	c = []
	p = 0
	for i in range(n):
		while p < n and l[p] <= i + 1:
			p += 1
		c.append(p)
	k = 0
	while f(k):
		k += 1
	if k > n // 2:
		k = (n + 1) // 2
	print(k)


t = int(input())
for num in range(t):
	n = int(input())
	bucket = [0] * (n + 2)
	a = [int(i) for i in input().split()]
	for i in a:
		bucket[i] += 1
	if bucket[1] == 0:
		print(0)
		continue
	if bucket[1] == 1:
		print(1)
		continue
	k = 2
	flag = []
	flag.append(1)
	while k <= n:
		if bucket[k] == 0:
			bucket[flag[-1]] -= 1
			if bucket[flag[-1]] == 1:
				z = flag.pop()
			bucket[k] = 1
			if bucket[1] < k:
				break
		if bucket[1] < k:
			break
		if bucket[k] >= 2:
			flag.append(k)
		k += 1
	print(k - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	x = input()
	y = str(x).split()
	y = [int(i) for i in y]
	y.sort()
	b = n
	for e in range(n):
		if y[e] > 1:
			b = e
			break
	for k in range(b, -1, -1):
		yy = [i for i in y]
		v = 0
		for i in range(k):
			a = k - i
			if yy[0] > a:
				v += 1
				break
			else:
				if yy[-1] <= a:
					del yy[-1]
				else:
					for d in range(1, len(yy)):
						if yy[d] > a:
							del yy[d - 1]
							break
				if len(yy) > 0:
					c = yy[0] + a
					del yy[0]
					yy.append(c)
		if v == 0:
			print(k)
			break


t = int(input())
for i in range(t):
	n = int(input())
	l = map(int, input().split())
	l = sorted(l)
	k = 1
	f = 1
	while f:
		l1 = l[:]
		for j in range(k - 1):
			del l1[0]
		coun = 0
		for j in range(k):
			coun += l1.count(j + 1)
			if coun < j + 1:
				f = 0
				break
		k += 1
	print(k - 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	axis = [0] * len(a)
	for i in a:
		axis[i - 1] += 1
	k_max = 0
	for k in range(axis[0], 0, -1):
		avail = axis[0] - k
		for i in range(1, k):
			if avail + axis[i] < 1:
				break
			else:
				avail += axis[i] - 1
		else:
			k_max = k
			break
	print(k_max)


import math
t = int(input())
for i in range(0, t):
	n = int(input())
	list1 = list(map(int, input().split()))
	list1.sort()
	if 1 not in list1:
		print(0)
	else:
		for q in range(math.ceil(n / 2), 0, -1):
			s = 1
			for r in range(q - 1, 2 * q - 1):
				if list1[r] <= s:
					s += 1
					continue
				else:
					break
			else:
				print(q)
				break


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a.append(n + 1)
	c = set(a)
	c = list(c)
	c.sort()
	b = a.count(1)
	if b == 0:
		print(0)
		continue
	elif b == 1:
		print(1)
		continue
	else:
		for k in range(b, -1, -1):
			ans = 0
			room = 1
			for i in range(len(c)):
				if c[i] > k:
					c[i] = k
					break
			for j in range(i - 1, 0, -1):
				room += c[j + 1] - c[j]
				p = a.count(c[j])
				if p <= room:
					ans += p
					room -= p
				else:
					ans += room
					room = 0
			ans += b
			if ans >= 2 * k - 1:
				break
		print(k)


n = int(input())
for i in range(n):
	m = int(input())
	hs = [int(x) for x in input().split()]
	t = hs.count(1)
	x = 0
	y = 0
	if t <= 1:
		print(str(t))
	else:
		ii = 2
		while ii <= t:
			tt = hs.count(ii)
			if tt == 0 and y == 0:
				t -= 1
			elif tt > 1:
				y += tt - 1
			elif tt == 0 and y > 0:
				y -= 1
			ii += 1
		print(str(t + x))


import math

def check(k: int):
	for j in range(k - 1, 2 * k - 1):
		if a[j] > j - k + 2:
			return 0
	return 1
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	ans = 0
	for i in range(math.ceil(n / 2) + 1):
		if check(i):
			ans = i
	print(ans)


n = int(input())
l = []
for _ in range(n):
	x = int(input())
	nn = [int(i) for i in input().split()]
	nn.sort()
	nn.append(0)
	o = nn.count(1)
	i = 1
	su = 0
	a = 0
	t = 0
	while i <= o and 2 * i - 2 < len(nn) - 1:
		a += nn[2 * i - 2] + nn[2 * i - 3]
		if nn[2 * i - 2] > i or a > i - 1 + int((i + 1) * i / 2):
			break
		else:
			t += 1
		i += 1
	l.append(t)
for x in l:
	print(x)


test = int(input())
for i in range(test):
	n = int(input())
	array = sorted([int(x) for x in input().split()])
	x1 = array.count(1)
	if x1 == 0:
		print(0)
	else:
		k = x1
		for j in range(x1):
			for s in range(k, 1, -1):
				zs = len([x for x in array if x <= s]) - k
				if zs < s - 1:
					k -= 1
					break
			else:
				ans = k
				print(k)
				break


for x in range(int(input())):
	b = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	if a.count(1) == 0:
		print(0)
	else:
		c = min(a.count(1), (b + 1) // 2)
		a.remove(1)
		for x in range(1, c + 1):
			if a.count(1) == 0:
				print(x)
				break
			else:
				a.remove(1)
				d = [y for y in a if y <= x + 1]
				if d == []:
					print(x)
					break
				else:
					a.remove(max(d))


a = int(input())
for i in range(a):
	b = int(input())
	c1 = [0] * b
	c2 = dict()
	c = list(map(int, input().split()))
	for i in range(b):
		if c[i] not in c2.keys():
			c2[c[i]] = 1
		else:
			c2[c[i]] += 1
	if 1 not in c2.keys():
		print(0)
	else:
		c1[0] = 1
		c2[1] -= 1
		k = 1
		for i in range(2, b):
			if k >= c2[1] + 1:
				break
			if i in c2.keys():
				if k >= i - 1:
					c1[k:k + c2[i]] = [i] * c2[i]
					k += c2[i]
				else:
					k += 1
					c2[1] -= 1
			elif c1[i - 1] == 0:
				k += 1
				c2[1] -= 1
		print(min(c2[1] + 1, k))


t = int(input())
for x in range(t):
	n = int(input())
	S = list(map(int, input().split()))
	d = dict()
	d[1] = 0
	for i in S:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	Lsum = []
	sum = 0
	for i in range(1, d[1] + 1):
		if i in d:
			sum += d[i]
		Lsum.append(sum - i + 1)
	count = 0
	for m in range(1, d[1] + 1):
		for i in range(m):
			if Lsum[i] < m:
				count += 1
			if count != 0:
				print(m - 1)
				break
		if count != 0:
			break
	if count == 0:
		print(d[1])


a = int(input())
for i in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	d = 0
	if 1 in c:
		d += 1
		c.pop(c.index(1))
	while 1 in c:
		c.pop(c.index(1))
		for j in range(d + 1, 0, -1):
			if j in c:
				d += 1
				c.pop(c.index(j))
				break
	print(d)


import bisect
output = []
for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	k = a.count(1)
	while k > 0:
		flag = 1
		p = k
		while p >= 1:
			j = bisect.bisect(a, p)
			if j < k + p - 1:
				flag = 0
				break
			else:
				p -= 1
		if flag == 1:
			output.append(str(k))
			break
		else:
			k -= 1
	if k == 0:
		output.append(str(0))
print('\n'.join(output))


for dm1 in range(int(input())):
	n = int(input())
	nmbs = [int(dm2) for dm2 in input().split()]
	bck = [0] * 102
	for i in nmbs:
		bck[i] += 1
	if bck[1] < 2:
		print(bck[1])
		continue
	(k, flag) = (2, [1])
	while k <= n:
		if bck[k] == 0:
			bck[flag[-1]] -= 1
			if bck[flag[-1]] == 1:
				z = flag.pop()
			bck[k] = 1
		if bck[k] >= 2:
			flag.append(k)
		if bck[1] < k:
			break
		k += 1
	print(k - 1)


for _ in range(int(input())):
	n = int(input())
	arr = [int(t) for t in input().split()]
	arr.sort()
	ind = min(arr.count(1), (n + 1) // 2) - 1
	while ind > 0:
		flag = 0
		for j in range(ind, 2 * ind + 1):
			if arr[j] > j - ind + 1:
				flag = 1
		if flag == 1:
			ind -= 1
			continue
		break
	print(ind + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = [int(x) for x in input().split()]
	s.sort()
	q = 0
	p = []
	m = 0
	o = s.count(1)
	pa = 1
	ma = 0
	for i in range(o):
		m += s.count(i + 1)
		p.append(m)
	if o != 0:
		for x in range(1, o + 1):
			for g in range(2, x + 1):
				if p[g - 2] < x + g - 2:
					pa = 0
					break
				elif p[g - 1] < x + g - 1:
					pa = 0
					break
			if pa == 1:
				ma = x
		print(ma)
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	if l.count(1) == 0:
		print(0)
		continue
	c = min(l.count(1), (n + 1) // 2)
	l.remove(1)
	for j in range(1, c + 1):
		if l.count(1) == 0:
			print(j)
			break
		l.remove(1)
		d = [y for y in l if y <= j + 1]
		if d == []:
			print(j)
			break
		else:
			l.remove(max(d))


n = int(input())
for i in range(n):
	u = int(input())
	x = [int(a) for a in input().split()]
	x.sort()
	if x.count(1) == 0:
		print(0)
	elif x.count(1) == 1:
		print(1)
	else:
		for c in range((u + 1) // 2, -1, -1):
			for d in range(c):
				if c + d - 1 >= u:
					break
				if x[c + d - 1] <= d + 1:
					y = 0
				else:
					y = 1
					break
			if y == 0:
				print(c)
				break


for i in range(int(input())):
	n = int(input())
	lis = sorted(list(map(int, input().split())))
	for j in range(1, n + 1):
		num = n - j + 1
		out = -(-(n - j + 1) // 2)
		if 2 * lis[-j] - 1 <= num and lis.count(1) >= out:
			if sum(lis[:-j]) + lis[-j] <= (1 + out) * out // 2 + num - out:
				print(out)
				break
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	m = (n + 1) // 2
	A = [int(i) for i in input().split()]
	A.sort()
	b = []
	c = A.count(1)
	if c == 0:
		print(0)
		continue
	for i in range(c, n):
		if A[i] > i // 2 + 1:
			print(min(m, (i + 1) // 2))
			break
		else:
			m = min(m, i + 2 - A[i])
	else:
		print(m)


for f in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = [l.count(x) for x in range(1, int(n) + 1)]
	z = 0
	for i in range(l[0]):
		z = l[0] - i
		g = i
		for k in l[1:z]:
			g += k - 1
			if g < 0:
				break
		else:
			break
	print(z)


t = int(input())
for i in range(t):
	n = int(input())
	alist = [int(x) for x in input().split()]
	alist.sort()
	d = 0
	if alist == [1]:
		print(1)
	elif alist.count(1) == len(alist):
		print((n + 1) // 2)
	else:
		k = min(alist.count(1), n // 2 + 1)
		if k < 2:
			print(k)
		else:
			while d == 0:
				i = 0
				new = alist
				while i <= k:
					i += 1
					new = sorted([int(x) for x in new if x <= k - i + 1])
					if len(new) > 2:
						new = new[1:]
						new.pop()
					elif alist.count(1) == 0:
						k -= 1
						i = 2 * k
					elif k - i != 0:
						k -= 1
						i = 2 * k
					else:
						print(k)
						d -= 1
						i = 2 * k


for x in range(int(input())):
	n = int(input())
	a = sorted([int(y) for y in input().split()])
	for k in range(n, -1, -1):
		if all((k - 1 + i < n and a[k - 1 + i] <= i + 1 for i in range(k))):
			print(k)
			break


import bisect
for _ in range(int(input())):
	n = int(input())
	s = sorted(list(map(int, input().split())))
	i = 2
	if s[0] != 1:
		print(0)
	else:
		s.pop(0)
		while len(s) >= 2 and s[0] == 1:
			if bisect.bisect_left(s, i) == len(s):
				s.pop()
				s.pop(0)
			elif s[bisect.bisect_left(s, i)] == i:
				s.pop(bisect.bisect_left(s, i))
				s.pop(0)
			elif s[bisect.bisect_left(s, i)] > i and bisect.bisect_left(s, i) > 1:
				s.pop(bisect.bisect_left(s, i) - 1)
				s.pop(0)
			else:
				break
			i += 1
		print(i - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1 or n == 2:
		if arr.count(1) > 0:
			print(1)
		else:
			print(0)
		continue
	arr.sort()
	for i in range(1, (n + 1) // 2 + 1):
		flag = False
		for j in range(1, i + 1):
			if arr[i + j - 2] > j:
				flag = True
				break
		if flag:
			i -= 1
			break
	print(i)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	num = dict()
	for k in a:
		if k in num:
			num[k] += 1
		else:
			num[k] = 1
	lim = math.ceil(n / 2)
	if 1 in num:
		one = num[1]
	else:
		one = 0
	k_tmp = min(lim, one)
	k_ans = k_tmp
	flag = True
	while flag:
		left_one = one - k_ans + 1
		other = left_one
		for x in range(2, n + 1):
			if x in num:
				other += num[x]
			elif other >= x:
				continue
			else:
				break
		if other >= k_ans:
			flag = False
		else:
			k_ans -= 1
	print(k_ans)


n = int(input())
for i in range(n):
	N = 0
	m = int(input())
	list1 = list(map(int, input().split()))
	list1.sort()
	if m % 2 == 0:
		list1.pop(-1)
		m -= 1
	k = int((m + 1) / 2)
	l = 0
	j = k
	for i in range(k):
		list2 = []
		if j == 1:
			if list1[0] == 1:
				print(1)
			else:
				print(0)
		else:
			if list1.count(1) >= j:
				for f in range(j - 1):
					list2.append([f + 2, list1[f + j]])
				for f in range(j - 1):
					if list2[f][0] < list2[f][1]:
						break
					elif f == j - 2:
						print(j)
						N = 1
			if N:
				break
		j -= 1


t = int(input())
for i in range(0, t):
	n = int(input())
	m = [int(i) for i in input().split()]
	k = m.count(1)
	j = k
	u = 2
	while u <= k:
		j = j + m.count(u) - 1
		u += 1
		if j < k:
			k = j
	print(k)


from bisect import bisect_right

def play(n, a):
	(low, high) = (1, n)
	k = 0
	while low <= high:
		if alice_win(a, high):
			return high
		mid = (low + high) // 2
		if alice_win(a, mid):
			low = mid + 1
			high -= 1
			k = mid
		else:
			high = mid - 1
	return k

def alice_win(a: list, k: int):
	for i in range(k):
		j = bisect_right(a, k - i)
		a = a[:j]
		if len(a) == 0:
			return False
		a.pop()
		if len(a) > 0:
			a.pop(0)
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted([int(x) for x in input().split()])
	k = play(n, a)
	print(k)


import sys
t = int(sys.stdin.readline())

def check(k, n):
	ci = 0
	i = n - 1
	ji = 0
	j = 0
	while j <= i:
		if a[i] <= k - ji:
			ji += 1
			ci += 1
			j += 1
		i -= 1
	return ci
for _ in range(t):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	if n == 1 and a == [1]:
		print(1)
	else:
		l = 0
		r = n
		a.sort()
		while l <= r:
			mid = (l + r) // 2
			if check(mid, n) >= mid:
				l = mid + 1
			else:
				r = mid - 1
		print(min(l, mid, r))


R = lambda : map(int, input().split())
L = lambda : list(R())
for _ in range(int(input())):
	(n,) = R()
	l = sorted(L())
	k = (n + 1) // 2
	while k > 0:
		prev = 0
		for i in range(k):
			prev += l.count(i + 1)
			if prev < k + i:
				break
		else:
			break
		k -= 1
	else:
		print(0)
		continue
	print(k)


t = int(input())
for _ in range(t):
	n = int(input())
	lis = [int(x) for x in input().split(' ')]
	lis.sort()
	num = lis.count(1)
	s = min(num, n // 2 + n % 2)
	flag = False
	for i in range(1, s + 1):
		list1 = lis[i - 1:2 * i - 1]
		for j in range(i):
			if list1[j] > j + 1:
				flag = True
				break
		if flag:
			s = i - 1
			break
	print(s)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(1)
	else:
		c = a.count(1)
		k = 2
		xx = 0
		j = 0
		cc = c
		nx = 0
		while c > 0:
			if c == 1:
				xx += 1
				c -= 1
			else:
				x = a.count(k)
				nx += x
				if x == 0:
					if nx + cc % 2 < k - 1:
						c -= 2
						xx += 1
					else:
						xx += 1
						c -= 1
					if nx + cc % 2 >= k - 1 and nx < k - 1:
						c -= 1
				elif x < c:
					c -= x
					xx += x
				else:
					xx += c
					c -= c
				k += 1
		print(xx)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	s.sort()
	k = (n + 1) // 2
	c = s.count(1)
	if c == 0:
		print(0)
		continue
	for i in range(c, n):
		if s[i] > i // 2 + 1:
			print(min(k, (i + 1) // 2))
			break
		else:
			k = min(k, i + 2 - s[i])
	else:
		print(k)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	k = 0
	for i in range((n + 1) // 2):
		true = True
		for j in range(i + 1):
			if a[i + j] > j + 1:
				true = False
		if true:
			k += 1
		else:
			break
	print(k)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(ii) for ii in input().split()]
	a.sort()
	ans = 0
	for i in range((n + 1) // 2):
		stop = 0
		for j in range(i + 1):
			if a[i + j] > j + 1:
				stop = 1
				break
		if stop:
			break
		else:
			ans += 1
	print(ans)


from collections import Counter
for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	c = Counter(a)
	for k in range(len(a) + 1):
		cnt = 0
		for i in range(k + 1):
			cnt += c[i + 1]
			if cnt < k + i + 1:
				break
		else:
			continue
		print(k)
		break


def analog(x):
	(synA, synB) = (x, 1)
	for round in range(1, x + 1):
		synA = x - round + 1
		while bck[synA] == 0 and synA > 1:
			synA -= 1
		bck[synA] -= 1
		if round < x:
			bck[1] -= 1
	return [0, 1][bck[1] >= 0]
for dm1 in range(int(input())):
	n = int(input())
	nmbs = sorted([int(x) for x in input().split()])
	bckk = [0] * 102
	for i in nmbs:
		bckk[i] += 1
	(lo, hi) = (0, 100)
	if bckk[1] in {0, 1}:
		print(bckk[1])
	else:
		while lo < hi:
			bck = bckk[:]
			mid = (lo + hi) // 2
			if analog(mid) == 1:
				lo = mid + 1
			else:
				hi = mid
		print(lo - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted([int(x) for x in input().split()])
	k = 0
	while True:
		if 2 * k - 1 <= n and all([a[k - 1 + i] <= 1 + i for i in range(k)]):
			k += 1
		else:
			k -= 1
			break
	print(k)


def check(k: int) -> bool:
	(l, r) = (0, n - 1)
	i = 0
	while i < k and l <= r:
		while l <= r and arr[r] > k - i:
			r -= 1
		if arr[r] > k - i or r < l:
			break
		r -= 1
		l += 1
		i += 1
	return i >= k
for _ in range(int(input())):
	n = int(input())
	arr = list(sorted(map(int, input().split())))
	(l, r) = (-1, n + 1)
	while l + 1 < r:
		m = (l + r) // 2
		if check(m):
			l = m
		else:
			r = m
	print(l)


def check(arr, t):
	j = 0
	temp = t
	count = 0
	for i in range(len(arr) - 1, -1, -1):
		if arr[i] <= t:
			arr[i] = 0
			arr[j] += t
			j += 1
			t -= 1
			count += 1
	if count == temp:
		return True
	return False

def ans(arr):
	start = 0
	end = 10 * 5
	arr.sort()
	current = 0
	while start <= end:
		temp = arr.copy()
		mid = (start + end) // 2
		if check(temp, mid) is True:
			current = mid
			start = mid + 1
		else:
			end = mid - 1
	return current
test_cases = int(input())
while test_cases != 0:
	d = input()
	d2 = list(map(int, input().split()))
	print(ans(d2))
	test_cases -= 1


t = int(input())
while t:
	n = int(input())
	ans = 0
	a = [0]
	a += list(map(int, input().split()))
	a.sort()
	for k in range(1, n + 2):
		l = 0
		r = n
		flag = 1
		for i in range(1, k + 1):
			while a[r] > k - i + 1:
				r -= 1
				if l == r:
					break
			if l == r:
				break
			r -= 1
			if i == k:
				flag = 0
			if l == r:
				break
			l += 1
			if l == r:
				break
		if flag:
			ans = k - 1
			break
	print(ans)
	t -= 1


import copy
a = int(input())
for i in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	d = c.copy()
	if 1 not in c:
		print('0')
	elif b == 1:
		print('1')
	else:
		for k in range(2, b + 1):
			c = d.copy()
			f = 1
			for n in range(k, 0, -1):
				c.append(n + 1)
				c.sort()
				e = c.index(n + 1)
				if e == 0:
					f = 0
					break
				else:
					c[0] += n
				del c[e - 1]
			if f == 0:
				print(k - 1)
				break


import copy
t = int(input())
for o in range(t):
	n = int(input())
	array = [int(x) for x in input().split()]
	one = array.count(1)
	p = 0
	c = True
	for k in range(one, 0, -1):
		if c is False:
			break
		a = copy.copy(array)
		a.sort(reverse=True)
		for i in range(k, 0, -1):
			if a.count(1) < i:
				break
			elif i > 1:
				for j in range(len(a)):
					if a[j] <= i:
						del a[j]
						a[-1] += i
						a.sort(reverse=True)
						break
			elif 1 in array:
				print(k)
				c = False
	if c:
		print('0')


t = int(input())
for _ in range(t):
	n = int(input())
	game = list(map(int, input().split()))
	game.sort()
	k = 0
	bl = True
	while bl:
		k += 1
		a = []
		m = 1
		for i in range(n):
			if game[i] <= k:
				a.append(game[i])
		if len(a) == 0:
			bl = False
		else:
			for j in range(1, len(a) + 1):
				if a[-j] <= k - m + 1:
					m += 1
					if m == k + 1 and len(a) - j < k - 1:
						bl = False
			if m <= k:
				bl = False
	print(k - 1)


def evaluate(lis, k):
	for i in range(k):
		if lis[k - 1 + i] > i + 1:
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	array = sorted(list(map(int, input().split())))
	k_approx = (n + 1) // 2 + 1
	alice_win = False
	while alice_win is False:
		k_approx -= 1
		if k_approx == 0:
			alice_win = True
			print(0)
			break
		else:
			alice_win = evaluate(array, k_approx)
			if alice_win:
				print(k_approx)
				break


import sys
import math
from bisect import bisect_right as br
import threading

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	arr.sort()
	i = 0
	j = n
	ans = 0
	while i <= j:
		mid = (i + j) // 2
		x = mid
		l = 0
		r = n - 1
		step = 0
		while l <= r:
			while r >= l and arr[r] > x:
				r -= 1
			if r < l or arr[r] > x:
				break
			step += 1
			x -= 1
			l += 1
			r -= 1
		if step >= mid:
			ans = mid
			i = mid + 1
		else:
			j = mid - 1
	print(ans)


import math
t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = 0
	for k in range(0, 1 + math.ceil(n / 2)):
		if arr.count(1) >= k:
			extra = arr.count(1) - k
			brr = arr[k:]
			p = 0
			for i in range(0, k - 1):
				if not brr[i] <= i + 2:
					p = 1
					break
			if p == 0:
				ans = max(ans, k)
	print(ans)
while t:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	num.sort()
	(l, r, ans) = (0, n, 0)

	def ck(m):
		res = []
		k = m
		for i in num:
			if i <= m:
				res.append(i)
		while len(res) > 0 and k > 0:
			res.pop()
			if len(res) > 0:
				res[0] += k
				res.sort()
			k -= 1
			while res and res[-1] > k:
				res.pop()
		return True if k == 0 else False
	if n == 1:
		print(1)
	else:
		while l <= r:
			m = (l + r) // 2
			if ck(m):
				ans = max(ans, m)
				l = m + 1
			else:
				r = m - 1
		print(ans)


n = int(input())
for i in range(n):
	x = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	for k in range(int((x + 1) // 2), -1, -1):
		s = 0
		for j in range(k):
			if lst[k - 1 + j] <= j + 1:
				s += 1
		if s == k:
			print(k)
			break