Chef gives you a sequence A of length N.  
Let X denote the MEX of the sequence A. Chef is interested in the count of positive values k, such that, if every element A_{i} of A is replaced by \texttt{max}(A_{i}-k,0), the MEX of the sequence still remains X.

Find the count of such values. If there are infinite such values, print -1 instead.

As a friendly reminder, the MEX of a sequence is the smallest non-negative integer that does not belong to the sequence. For instance:

The MEX of [2,2,1] is 0 because 0 does not belong to the sequence.
The MEX of [3,1,0,1] is 2 because 0 and 1 belong to the sequence, but 2 does not.

------ Input Format ------ 

- 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 length of the sequence A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

------ Output Format ------ 

For each test case print a single integer — the count of positive values k satisfying the given condition. If there are infinite such values, print -1 instead.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{9} $
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
1 2 3 5
1
0
7
5 10 2 4 0 6 1
----- Sample Output 1 ------ 
0
-1
1
----- explanation 1 ------ 
- Test case $1$: There doesn't exist any value of $k$ satisfying the given condition.
- Test case $2$: There are infinite values of $k$ satisfying the given condition.
- Test case $3$: There is only $1$ value of $k$ satisfying the given condition: $k=4$. The $MEX$ of the given sequence is $3$. When every element $A_{i}$ of the given sequence is replaced by $max(A_{i}-4,0)$, the sequence becomes $[1, 6, 0, 0, 0, 2, 0]$, which also has $MEX=3$.

Difficulty: HARD

Starter code:

Solutions:
import math
import bisect
for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	b = list(set(A))
	b.sort()
	d = len(b)
	mex = 0
	k = 0
	while k < d:
		if b[k] != k:
			mex = k
			break
		else:
			if k == d - 1:
				mex = d
			k += 1
	if mex == 0:
		c = b[0]
		print(c - 1)
	elif mex == 1:
		print(-1)
	elif mex == 2:
		c = 0
		for k in range(1, d):
			if b[k] < mex:
				pass
			elif b[k] - b[k - 1] == 1:
				c += 1
		print(d - 2 - c)
	else:
		c = 0
		count = 1
		y = 0
		k = 0
		n = d
		while k < n:
			if b[k] < mex:
				k += 1
			elif b[k] - b[k - 1] == 1:
				if y == 0:
					y = 1
					count += 1
				else:
					count += 1
				if k == n - 1:
					if y == 1 and count >= mex - 1:
						c += 1
						k += 1
					else:
						k += 1
				else:
					k += 1
			elif y == 0:
				k += 1
			elif y == 1 and count >= mex - 1:
				c += 1
				count = 1
				y = 0
				k += 1
			else:
				y = 0
				count = 1
				k += 1
		print(c)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	a.sort()
	mex = 0
	for v in a:
		if v == mex:
			mex += 1
		elif v > mex:
			break
	ans = 0
	if mex == 0:
		ans = a[0] - 1
	elif mex == 1:
		ans = -1
	else:
		i = 0
		cnt = 0
		v = a[i]
		while i < n:
			if v == a[i]:
				v += 1
				i += 1
				cnt += 1
			elif v < a[i]:
				ans += 1 if cnt >= mex - 1 else 0
				v = a[i]
				cnt = 0
			else:
				i += 1
		ans += 0 if cnt >= mex - 1 else -1
	print(ans)


def fun(l):
	s = set(l)
	mex = 0
	while mex in s:
		mex += 1
	return mex
for _ in range(int(input())):
	n = int(input())
	l = list(set(list(map(int, input().split()))))
	l.sort()
	mex = fun(l)
	if mex == 1:
		print(-1)
	elif mex == 0:
		print(l[0] - 1)
	else:
		i = 0
		ans = 0
		n = len(l)
		count = 1
		if mex == n:
			count = 0
		else:
			count = 1
		for i in range(mex, n - 1):
			if l[i + 1] - l[i] == 1:
				count += 1
			else:
				if count >= mex - 1:
					ans += 1
				count = 1
		if count >= mex - 1:
			ans += 1
		print(ans)


for _ in range(int(input())):
	n = int(input())
	t = list(map(int, input().split()))
	k = set(t)
	l = list(k)
	point = -1
	l.sort()
	for i in range(len(l)):
		if l[i] != i:
			point = i
			break
	if point == -1:
		point = l[len(l) - 1] + 1
	count = 1
	ans = 0
	for i in range(point, len(l)):
		if i < len(l) - 1 and l[i] + 1 == l[i + 1]:
			count += 1
		else:
			if count >= point - 1:
				ans += 1
			count = 1
	if point == 1:
		print(-1)
	elif point == 0:
		print(l[0] - 1)
	elif point == n:
		print(0)
	else:
		print(ans)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	a = list(set(a))
	if 0 not in a:
		print(min(a) - 1)
	elif 1 not in a:
		print(-1)
	else:
		a.sort()
		cont = []
		l = 1
		mex = -1
		for i in range(1, len(a)):
			if a[i] == a[i - 1] + 1:
				l += 1
			else:
				cont.append(l)
				l = 1
		if l != 0:
			cont.append(l)
		ans = -1
		for c in cont:
			if c >= cont[0] - 1:
				ans += 1
		print(ans)


import sys
from itertools import islice, groupby
for s in islice(sys.stdin, 2, None, 2):
	a = sorted(set(map(int, s.split())))
	r = a[0] - 1
	if a[0] == 0:
		b = (len([*g]) for (k, g) in groupby((x - i for (i, x) in enumerate(a))))
		m = next(b) - 1
		if m:
			r = sum((x >= m for x in b))
	print(r)


def mex(a):
	(n, s, m) = (len(a), set(a), 0)
	while m in s and m < n:
		m += 1
	return m
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = mex(a)
	a = sorted(set(a))
	(k, nn) = (0, len(a))
	clens = []
	while k < nn:
		p = c = a[k]
		j = k
		k += 1
		while k < nn and a[k] == p + 1:
			p += 1
			k += 1
		if c:
			clens.append(k - j)
	if not m:
		print(min(a) - 1)
	elif m == 1:
		print(-1)
	else:
		print(sum((1 for x in clens if x >= m)) + clens.count(m - 1))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mex = 0
	count = 1
	ans = 0
	arr.sort()
	for i in arr:
		if i == mex:
			mex += 1
	if mex == 0:
		ans = min(arr) - 1
	elif mex == 1:
		ans = -1
	else:
		for i in range(len(arr) - 1):
			if arr[i] + 1 == arr[i + 1] or arr[i] == arr[i + 1]:
				if arr[i] + 1 == arr[i + 1]:
					count += 1
			else:
				if count >= mex - 1:
					ans += 1
				count = 1
		if count >= mex - 1:
			ans += 1
		ans -= 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	mex = 0
	if l[0] == 0:
		mex = 1
		for x in range(1, n):
			if l[x] == mex - 1:
				continue
			elif l[x] == mex:
				mex = mex + 1
			else:
				break
	if mex == 1:
		print('-1')
	elif l[0] != 0:
		print(l[0] - 1)
	else:
		ans = 0
		cnt = 1
		for x in range(n - 1):
			if l[x] + 1 == l[x + 1]:
				cnt = cnt + 1
			elif l[x] == l[x + 1]:
				continue
			else:
				if cnt >= mex - 1:
					ans = ans + 1
				cnt = 1
		if cnt >= mex - 1:
			ans = ans + 1
		print(ans - 1)


def create_contagious(arr):
	blocks = []
	(a, b) = (0, 1)
	while b < len(arr):
		if arr[b] - arr[b - 1] == 1:
			b += 1
		else:
			blocks.append(arr[a:b])
			a = b
			b += 1
		if b == len(arr):
			blocks.append(arr[a:b])
	return blocks

def solve(A: list):
	A = list(set(A))
	A.sort()
	if A[0] >= 1:
		return A[0] - 1
	elif A[0] == 0 and 1 not in A:
		return -1
	blocks = create_contagious(A)
	total_k = 0
	MEX = blocks[0][-1] + 1
	for (i, nums) in enumerate(blocks):
		if i == 0:
			continue
		if len(nums) >= MEX - 1:
			total_k += 1
	return total_k

def main():
	T = int(input())
	for tc in range(T):
		n = int(input())
		A = list(map(int, input().split()))
		ans = solve(A)
		print(ans)
main()


for _ in range(int(input())):
	n = int(input())
	a = sorted(list(set(map(int, input().split()))))
	if a[-1] == 0:
		print(-1)
		continue
	target = -1
	for (i, v) in enumerate(a):
		if i != v:
			target = i
			break
	if target == 0:
		print(a[0] - 1)
		continue
	elif target == -1:
		print(0)
		continue
	elif target == 1:
		print(-1)
		continue
	countList = []
	count = 1
	for i in range(target, len(a) - 1):
		if a[i] + 1 == a[i + 1]:
			count += 1
		elif a[i] != a[i + 1]:
			countList.append(count)
			count = 1
	countList.append(count)
	ans = 0
	for i in countList:
		if i >= target - 1:
			ans += 1
	print(ans)


def get_mex(B):
	se = set(B)
	n = len(B)
	for i in range(n + 1):
		if i not in se:
			return i
for _ in range(int(input())):
	n = int(input())
	A = [int(x) for x in input().split()]
	mex = get_mex(A)
	if mex == 0:
		print(min(A) - 1)
	elif mex == 1:
		print(-1)
	else:
		A = list(set(A))
		n = len(A)
		A.sort()
		ans = 0
		i = 0
		while i < n:
			j = i
			while j < n - 1 and A[j + 1] - A[j] == 1:
				j += 1
			if j - i + 1 >= mex - 1:
				ans += 1
			i = j + 1
		print(ans - 1)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	lis.sort()
	res = [lis[0]]
	for i in lis:
		if i != res[-1]:
			res.append(i)
	mex = 0
	ans = 0
	for i in res:
		if i == mex:
			mex += 1
		else:
			break
	if mex == 0:
		print(res[0] - 1)
	elif mex == 1:
		print(-1)
	elif mex > res[-1]:
		print(0)
	elif mex == len(res):
		print(0)
	else:
		le = len(res)
		p1 = mex
		while p1 < le:
			start = p1
			p1 += 1
			while p1 < le and res[p1] == res[p1 - 1] + 1:
				p1 += 1
			if p1 - start >= mex - 1:
				ans += 1
		print(ans)


from collections import Counter
for t in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr_ = set(arr)
	arr = sorted(list(arr_))
	mex = 0
	ind = 0
	for i in arr:
		if i == mex:
			mex += 1
			ind += 1
		else:
			break
	if mex == 1:
		print(-1)
	elif mex == 0:
		print(min(arr) - 1)
	elif mex == len(arr):
		print(0)
	elif mex == 2:
		ans = 0
		if len(arr) - 1 == ind:
			print(1)
			continue
		cnt = 1
		for i in range(ind + 1, len(arr)):
			if arr[i] == arr[i - 1] + 1:
				cnt += 1
				if i == len(arr) - 1:
					ans += 1
			else:
				if cnt >= mex - 1:
					ans += 1
				cnt = 1
				if i == len(arr) - 1:
					ans += 1
		print(ans)
	else:
		ans = 0
		cnt = 1
		for i in range(ind + 1, len(arr)):
			if arr[i] == arr[i - 1] + 1:
				cnt += 1
			else:
				if cnt >= mex - 1:
					ans += 1
				cnt = 1
			if i == len(arr) - 1:
				if cnt >= mex - 1:
					ans += 1
		print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = list(set(a))
	a.sort()
	n = len(a)
	mex = 0
	for i in a:
		if i != mex:
			break
		else:
			mex += 1
	if mex == 1:
		print(-1)
		continue
	if mex == 0:
		print(min(a) - 1)
		continue
	l = 2
	count = 0
	for i in range(1, n - 1):
		if a[i] + 1 == a[i + 1]:
			l += 1
		else:
			if l >= mex - 1:
				count += 1
			l = 1
	if l >= mex - 1:
		count += 1
	print(count - 1)


def fun(n, l):
	x = 0
	s = set()
	for i in range(n):
		s.add(l[i])
		while x in s:
			x += 1
	return x
for _ in range(int(input())):
	n = int(input())
	l = set(list(map(int, input().split())))
	s = l
	l = list(l)
	l.sort()
	n = len(l)
	x = fun(n, l)
	val = 0
	ans = 0
	i = 0
	while i < n:
		if i == l[i]:
			i += 1
		else:
			break
	while i < n:
		y = l[i]
		f = 0
		while i < n and y + f == l[i]:
			i += 1
			f += 1
		if f >= x - 1:
			ans += 1
	if x == 0:
		print(min(l) - 1)
	elif x == 1:
		print(-1)
	else:
		print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = list(set(l))
	l.sort()
	mex = 0
	ind = -1
	for i in range(len(l)):
		if l[i] == mex:
			mex += 1
		else:
			ind = i
			break
	if mex == 0:
		print(min(l) - 1)
		continue
	if mex == 1:
		print(-1)
		continue
	cou = 1
	tot = 0
	for i in range(len(l) - 1):
		if l[i] + 1 == l[i + 1]:
			cou += 1
		else:
			if cou >= mex - 1:
				tot += 1
			cou = 1
	if cou >= mex - 1:
		tot += 1
	print(tot - 1)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	i = 0
	x = 0
	a = list(dict.fromkeys(a))
	a.sort()
	n = len(a)
	while i < n and x == a[i]:
		x += 1
		i += 1
	if x == 0:
		print(a[0] - 1)
	elif x == 1:
		print(-1)
	else:
		k = 0
		r = 1
		i = 0
		while i < n - 1:
			r += 1
			if a[i + 1] != a[i] + 1:
				if r >= x - 1:
					k += 1
				r = 0
			i += 1
		r += 1
		if r >= x - 1:
			k += 1
		k -= 1
		print(k)


def findmex(l):
	m = 0
	for i in l:
		if i != m:
			break
		m += 1
	return m
t = int(input())
for _ in range(t):
	_ = input()
	l = list(map(lambda x: int(x), input().split()))
	l = sorted(list(dict.fromkeys(l)))
	mex = findmex(l)
	if mex == 0:
		print(min(l) - 1)
	elif mex == 1:
		print(-1)
	else:
		ans = -1
		i = 0
		while i < len(l):
			cnt = 1
			j = i + 1
			while j < len(l) and l[j - 1] + 1 == l[j]:
				cnt += 1
				j += 1
			if cnt >= mex - 1:
				ans += 1
			i = j
		print(ans)


from itertools import count
import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if l.count(0) == 0:
		print(min(l) - 1)
	elif l.count(1) == 0:
		print(-1)
	else:
		a = list(set(l))
		a.sort()
		x = 1
		ans = []
		for i in range(len(a) - 1):
			if a[i] + 1 == a[i + 1]:
				x = x + 1
			else:
				ans.append(x)
				x = 1
		ans.append(x)
		c = 0
		for i in range(1, len(ans)):
			if ans[i] >= ans[0] - 1 and ans[i] > 0:
				c = c + 1
		print(c)


import math

def mex(a):
	for x in range(len(a) + 1):
		if x not in a:
			return x
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	if 0 not in a:
		print(min(a) - 1)
	elif 1 not in a:
		print(-1)
	else:
		b = set(a)
		m = mex(b)
		ans = 0
		seq_len = 1
		a = list(b)
		a = sorted(a)
		for x in range(1, len(a)):
			if a[x] == a[x - 1] + 1:
				seq_len += 1
			else:
				if seq_len >= m - 1:
					ans += 1
				seq_len = 1
		if seq_len >= m - 1:
			ans += 1
			seq_len = 1
		print(ans - 1)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	lis1 = list(map(int, input().split()))
	lis1.sort()
	lis = [lis1[0]]
	for i in range(1, n):
		if lis1[i] != lis1[i - 1]:
			lis.append(lis1[i])
	n = len(lis)
	mex = lis[-1] + 1
	for i in range(n):
		if lis[i] != i:
			mex = i
			break
	if mex == 0:
		print(lis[0] - 1)
		continue
	if n == 1:
		print(-1)
		continue
	if lis[1] != 1:
		print(-1)
		continue
	total = 0
	k = mex
	i = mex
	while i < n:
		coun = 1
		i = i + 1
		while i < n:
			if lis[i] == lis[i - 1] + 1:
				coun += 1
				i += 1
			else:
				break
		if coun >= mex - 1:
			total += 1
	print(total)


t = int(input())
for _ in range(t):
	input()
	A = list(set([int(x) for x in input().split(' ')]))
	A.sort()
	if 0 not in A:
		print(min(A) - 1)
		continue
	if 1 not in A:
		print(-1)
		continue
	mex = 0
	for i in range(len(A)):
		if i != A[i]:
			mex = i
			break
	if mex == 0:
		mex = A[-1] + 1
	A.append(A[-1] + 1000)
	mex -= 1
	count = -1
	for i in range(len(A) - mex):
		if A[i + mex - 1] == A[i] + mex - 1 and A[i + mex - 1] != A[i + mex] - 1:
			count += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	arr1 = list(map(int, input().split(' ')))
	arr1.sort()
	arr = [arr1[0]]
	for i in range(1, n):
		if arr1[i] == arr[-1]:
			continue
		arr.append(arr1[i])
	pointer = -1
	mex = 0
	for i in range(len(arr)):
		if arr[i] == mex:
			mex += 1
			continue
		if arr[i] > mex:
			pointer = i
			break
	if pointer == -1:
		pointer = len(arr)
	cont = 1
	ans = 0
	if mex == 0:
		print(arr[0] - 1)
		continue
	if mex == 1:
		print(-1)
		continue
	if mex == len(arr):
		print(0)
		continue
	for i in range(pointer + 1, len(arr)):
		if arr[i] == arr[i - 1] + 1:
			cont += 1
		else:
			if cont >= mex - 1:
				ans += 1
			cont = 1
	if cont >= mex - 1:
		ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	a = set(arr)
	m = 0
	while True:
		if m in a:
			m += 1
		else:
			break
	if m == 1:
		print(-1)
	elif m == 0:
		print(arr[0] - 1)
	else:
		i = 0
		while i < n and arr[i] < m:
			i += 1
		if i >= n:
			print(0)
			continue
		ans = 0
		l = m - 1
		curr = 1
		a = arr[i]
		while i < n:
			if arr[i] == a:
				i += 1
			else:
				if arr[i] == a + 1:
					curr += 1
					a += 1
				else:
					if curr >= l:
						ans += 1
						curr = 1
					curr = 1
					a = arr[i]
				i += 1
		if curr >= l:
			ans += 1
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(s) for s in input().split(' ')]
	a = list(set(a))
	a.sort()
	n = len(a)
	ans = 0
	mex = 0
	cur = 0
	temp = []
	if a[0] != 0:
		print(a[0] - 1)
		continue
	if n == 1:
		print(-1)
		continue
	if a[1] != 1:
		print(-1)
		continue
	cnt = 1
	for i in range(n - 1):
		if a[i] + 1 != a[i + 1]:
			temp.append(cnt)
			cnt = 1
		else:
			cnt += 1
	if cnt:
		temp.append(cnt)
	for i in range(n):
		if a[i] != cur:
			mex = cur
			break
		else:
			cur += 1
	else:
		print(0)
		continue
	for i in range(len(temp)):
		if i == 0:
			continue
		if temp[i] >= mex - 1:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(set(map(int, input().split(' '))))
	n = len(a)
	a.sort()
	b = []
	if a[0] != 0:
		print(a[0] - 1)
		continue
	(j, ans, k) = (0, 0, 0)
	for i in range(n):
		if a[i] != j:
			j = a[i]
			b.append(k)
			k = 0
		j += 1
		k += 1
	b.append(k)
	if n == 1 or b[0] == 1:
		print(-1)
		continue
	for i in range(len(b)):
		if b[i] >= b[0] - 1:
			ans += 1
	print(ans - 1)


from sys import stdin
input = stdin.readline

def mex(A):
	for (i, a) in enumerate(A):
		if a > i:
			return i
	return A[-1] + 1

def solve(N, A):
	A = sorted(list(set(A)))
	N = len(A)
	m = mex(A)
	if m == 0:
		return A[0] - 1
	if m == 1:
		return -1
	if m == 2:
		good = 0
		for i in range(2, N):
			if i == N - 1:
				good += 1
			elif A[i + 1] - A[i] >= 2:
				good += 1
		return good
	good = 0
	i = m
	while i + m - 2 <= N - 1:
		ok = True
		for j in range(1, m - 1):
			if A[i + j] != A[i] + j:
				ok = False
				break
		if ok and i + m - 1 < N:
			ok = A[i + m - 1] > A[i] + m - 1
		if ok:
			good += 1
		i += 1
	return good
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()]
	print(solve(N, A))


from bisect import bisect_left

def bn(a, x):
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def check(st, k, x):
	if k <= 0:
		return 0
	it = bn(st, k + 1)
	it2 = bn(st, k + x - 1)
	if it == -1 or it2 == -1:
		return 0
	cnt = it2 - it + 1
	if cnt == x - 1:
		it = bn(st, k + x)
		if it == -1:
			return 1
		return 0
	return 0
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr = set(arr)
	arr = list(arr)
	arr.sort()
	mex = 0
	n = len(arr)
	for i in range(n):
		if arr[i] == mex:
			mex += 1
		else:
			break
	if mex == 0:
		print(max(0, arr[0] - 1))
	elif mex == 1:
		print(-1)
	if mex <= 1:
		continue
	ans = []
	for i in arr:
		ind1 = check(arr, i, mex)
		ind2 = check(arr, i - 1, mex)
		if ind1 == 1:
			ans.append(i)
		if ind2 == 1:
			ans.append(i - 1)
	print(len(set(ans)))


from collections import defaultdict as dd

def solve(lst, n):
	dk = dd(int)
	for x in lst:
		dk[x] = 1
	for x in range(1 + n):
		if not dk[x]:
			return x
for _ in range(int(input())):
	n = int(input())
	lst_ = list(map(int, input().split()))
	lst_.sort()
	lst = []
	prev = -1
	n = 0
	for x in lst_:
		if x != prev:
			lst.append(x)
			n += 1
		prev = x
	mex = solve(lst, n)
	req = mex - 1
	lst.append(0)
	if mex == 0:
		print(lst[0] - 1)
	elif mex == 1:
		print(-1)
	else:
		cnt = 1
		rslt = 0
		for x in range(n):
			if abs(lst[x] - lst[x + 1]) == 1:
				cnt += 1
			else:
				if cnt >= req:
					rslt += 1
				cnt = 1
		print(max(0, rslt - 1))


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	arr = sorted(list(set(arr)))
	n = len(arr)
	mex = n
	for i in range(n):
		if arr[i] != i:
			mex = i
			break
	if mex == 1:
		return -1
	if mex == n:
		return 0
	if mex == 0:
		return arr[0] - 1
	ans = 0
	i = mex
	while i < n:
		start = i
		i += 1
		while i < n and arr[i] == arr[i - 1] + 1:
			i += 1
		if i - start >= mex - 1:
			ans += 1
	return ans
t = int(input())
for i in range(t):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sa = set(a)
	a = sorted(list(sa))
	mex = None
	for i in range(len(a)):
		if i != a[i]:
			mex = i
			break
	if mex is None:
		mex = a[-1] + 1
	if mex == 0:
		print(a[0] - 1)
		continue
	if mex == 1:
		print(-1)
		continue
	prev = -100
	k_count = 0
	cont = 1
	for i in a:
		if i < mex:
			prev = i
			cont = -1
			continue
		if i - prev == 1:
			cont += 1
		else:
			if cont >= mex - 1:
				k_count += 1
			cont = 1
		prev = i
	if cont >= mex - 1:
		k_count += 1
	print(k_count)


def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res
mod = 10 ** 4

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def nextPowerOf2(n):
	count = 0
	if n and (not n & n - 1):
		return n
	while n != 0:
		n >>= 1
		count += 1
	return 1 << count
from collections import defaultdict
import math

def primeFactors(n):
	res = set()
	while n % 2 == 0:
		res.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			res.add(i)
			n = n // i
	if n > 2:
		res.add(n)
	return res

def upper_bound(arr, target):
	start = 0
	end = len(arr) - 1
	ans = -1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] <= target:
			start = mid + 1
		else:
			ans = mid
			end = mid - 1
	return ans

def get_dis(s1, s2):
	s = 'abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz'
	a1 = s.index(s1)
	a2 = s.rfind(s1)
	b1 = s.index(s2)
	b2 = s.rfind(s2)
	return min(abs(a1 - b1), abs(a1 - b2), abs(a2 - b1), abs(a2 - b2))
from collections import defaultdict

def func(l, m):
	ans = 0
	s = set()
	for ele in l:
		ans += ele % m
		print(ans, ele % m, ele, m)
		if ele % m in s:
			return -1
	print('tot', len(l) * (len(l) + 1) // 2, ans)
	if ans == len(l) * (len(l) + 1) // 2:
		return 1
	return 0

def printDivisors(n):
	i = 1
	res = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				res.append(i)
			else:
				res.append(i)
				res.append(n // i)
		i = i + 1
	return res
INF = 1000000000000000000000
from collections import deque

def solve():
	d = defaultdict(int)
	n = int(input())
	lis = list(map(int, input().split()))
	lis = list(set(lis))
	n = len(lis)
	lis.sort()
	if lis[0] == 0 and n == 1:
		print(-1)
		return
	if lis[0] != 0:
		print(lis[0] - 1)
		return
	mex = 0
	i = 0
	while i < n and lis[i] == mex:
		i += 1
		mex += 1
	if mex == 1:
		print(-1)
		return
	temp = []
	lis.append(10000000000000000)
	while i < len(lis):
		st = lis[i]
		c = 1
		j = i + 1
		while j < len(lis):
			if lis[j] == lis[j - 1] + 1:
				j += 1
				c += 1
			else:
				temp.append((st, c))
				break
		i = j
	ans = 0
	for (i, ele) in enumerate(temp):
		if ele[0] > mex and ele[1] >= mex - 1:
			ans += 1
	print(ans)
num_test = 1
num_test = int(input())
for _ in range(num_test):
	solve()


t = int(input())
for test in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	ans = 0
	i = 0
	st = set(lst)
	lst = list(st)
	n = len(lst)
	lst.sort()
	mex = n
	for i in range(n):
		if lst[i] != i:
			mex = i
			break
	if mex == 1:
		print('-1')
	elif mex == 0:
		print(lst[0] - 1)
	else:
		i = 0
		while i < n:
			ch = lst[i]
			cnt = 0
			t = lst[i]
			while i < n and lst[i] == t:
				t += 1
				cnt += 1
				i += 1
			if cnt >= mex - 1:
				ans += 1
		print(ans - 1)


for T in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A = list(set(A))
	N = len(A)
	A.sort()
	mex = 0
	st = -1
	for i in range(N):
		if A[i] == mex:
			mex += 1
		elif A[i] > mex:
			st = i
			break
		st = i + 1
	if mex == 1:
		print(-1)
	elif mex == 0:
		print(A[0] - 1)
	elif mex == 2:
		ans = 0
		for i in range(st, N):
			if A[i] - A[i - 1] > 1:
				ans += 1
		print(ans)
	else:
		ans = 0
		i = N - 1
		while i >= st:
			ct = 0
			if A[i] - A[i - 1] == 1:
				while A[i] - A[i - 1] == 1:
					i -= 1
					ct += 1
			else:
				i -= 1
			if ct >= mex - 2:
				ans += 1
		print(ans)


for _ in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	lis = list(set(s))
	lis.sort()
	mex = len(lis)
	for i in range(len(lis)):
		if lis[i] != i:
			mex = i
			break
	if mex == 0:
		print(min(s) - 1)
	elif mex == 1:
		print(-1)
	else:
		ans = 0
		i = 2
		if mex == 2:
			if lis[-1] - lis[-2] != 1:
				ans += 1
		while i < len(lis) - 1:
			count = 0
			while i + 1 < len(lis) and lis[i + 1] - lis[i] == 1:
				i += 1
				count += 1
			if count >= mex - 2:
				ans += 1
			i += 1
		print(ans)


from typing import Counter

def solve(n, l):
	if l == [0]:
		return -1
	d = Counter(l)
	if d[0] == 0:
		return min(l) - 1
	m = 0
	while d[m] != 0:
		m += 1
	if m == 1:
		return -1
	pre = [1] * n
	for i in range(1, n):
		if l[i] - 1 == l[i - 1]:
			pre[i] += pre[i - 1]
	return pre.count(m - 1) - 1
for _ in range(int(input())):
	n = int(input())
	l = sorted(list(set(map(int, input().split()))))
	n = len(l)
	print(solve(n, l))


from collections import Counter
quar = int(input())
for _ in range(quar):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a.append(10000000000000)
	co = Counter(a)
	mex = 0
	lm = -1
	ans = 0
	while co[mex]:
		mex += 1
	if mex == 1:
		print('-1')
	elif mex == 0:
		print(min(a) - 1)
	else:
		ans = 0
		k = 1
		for i in range(1, len(a)):
			if a[i] == a[i - 1] + 1:
				k += 1
			elif a[i] == a[i - 1]:
				continue
			else:
				if k >= mex - 1:
					ans += 1
				k = 1
		print(ans - 1)


import sys

def solve():
	(n,) = map(int, sys.stdin.readline().split())
	a = sorted(set(map(int, sys.stdin.readline().split())))
	n = len(a)
	pos = 0
	while pos < n and a[pos] == pos:
		pos += 1
	mex = pos
	if mex == 1:
		print(-1)
	elif mex == 0:
		print(a[pos] - 1)
	elif pos == n:
		print(0)
	else:
		res = 0
		max_gap = a[pos] - 1
		while pos < n:
			if a[pos] - a[pos - 1] > 1:
				max_gap = a[pos] - 1
			k = a[pos] - mex + 1
			if max_gap - k <= 0 and (pos + 1 >= n or a[pos + 1] - a[pos] > 1):
				res += 1
			pos += 1
		print(res)
(t,) = map(int, sys.stdin.readline().split())
for _ in range(t):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = list(set(a))
	b.sort()
	le = len(b)
	mex = 0
	i = 0
	while i < le:
		if b[i] != i:
			mex = i
			break
		else:
			if i == le - 1:
				mex = le
			i += 1
	if mex == 1:
		print(-1)
	elif mex == 0:
		print(a[0] - 1)
	elif mex == 2:
		a = b
		n = le
		c = 0
		for i in range(1, n):
			if a[i] < mex:
				pass
			elif a[i] - a[i - 1] == 1:
				c += 1
		print(n - 2 - c)
	else:
		i = 0
		c = 0
		tc = 1
		y = 0
		a = b
		n = le
		while i < n:
			if a[i] < mex:
				i += 1
			elif a[i] - a[i - 1] == 1:
				if y == 0:
					y = 1
					tc += 1
				else:
					tc += 1
				if i == n - 1:
					if y == 1 and tc >= mex - 1:
						c += 1
						i += 1
					else:
						i += 1
				else:
					i += 1
			elif y == 0:
				i += 1
			elif y == 1 and tc >= mex - 1:
				c += 1
				tc = 1
				y = 0
				i += 1
			else:
				y = 0
				tc = 1
				i += 1
		print(c)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mex = 0
	arr.sort()
	for i in range(n):
		if arr[i] == mex:
			mex += 1
	if mex == 0:
		print(arr[0] - 1)
	elif mex == 1:
		print(-1)
	else:
		c = 0
		no = mex
		cnt = 0
		mn = 0
		for i in range(n):
			if arr[i] > mn:
				if c >= 1:
					if cnt >= no - 1:
						c += 1
				elif cnt >= no:
					c += 1
				cnt = 1
				mn = arr[i] + 1
			elif arr[i] == mn:
				mn += 1
				cnt += 1
		if c >= 1:
			if cnt >= no - 1:
				c += 1
		elif cnt >= no:
			c += 1
		print(c - 1)


def solve() -> None:
	...
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(set(a))
	n = len(a)
	if a[0] != 0:
		print(a[0] - 1)
		return
	if 1 not in a:
		print(-1)
		return
	for i in range(n):
		if a[i] != i:
			mex = i
			break
	else:
		print(0)
		return
	count = 0
	now = 1
	for i in range(1, n):
		if a[i] == a[i - 1] + 1:
			now += 1
			continue
		count += now >= mex - 1
		now = 1
	count += now >= mex - 1
	print(count - 1)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	l = list(sorted(set(li())))
	N = len(l)
	m = N
	for i in range(N):
		if i != l[i]:
			m = i
			break
	if m == 0:
		pr(l[0] - 1)
		return
	if m == 1:
		pr(-1)
		return
	ans = 0
	cur = 1
	for i in range(N - 1):
		if l[i + 1] - l[i] == 1:
			cur += 1
		else:
			if cur + 1 >= m:
				ans += 1
			cur = 1
	if cur + 1 >= m:
		ans += 1
	ans -= 1
	pr(ans)
for _ in range(inp()):
	solve()


import math
from collections import Counter, defaultdict
import sys
mod = 10 ** 9 + 7
input = sys.stdin.readline
readInt = lambda : int(input().strip())
readfloat = lambda : float(input().strip())
readStr = lambda : input().strip()
intList = lambda : list(map(int, input().strip().split()))
intMap = lambda : map(int, input().strip().split())
floatList = lambda : list(map(float, input().strip().split()))
floatMap = lambda : map(float, input().strip().split())
strList = lambda : list(input().strip().split())

def print(*args, end='\n', sep=' '):
	for i in args:
		sys.stdout.write(str(i))
		sys.stdout.write(sep)
	sys.stdout.write(end)

def solve():
	arr = sorted(set(ar))
	if arr[0] != 0:
		return arr[0] - 1
	if 1 not in set(arr):
		return -1
	res = 0
	for i in range(1, len(arr)):
		if arr[i] != arr[i - 1] + 1:
			c = 1
			for j in range(i + 1, len(arr)):
				if arr[j] == arr[j - 1] + 1:
					c += 1
				else:
					if c >= i - 1:
						res += 1
					c = 1
			if c >= i - 1:
				res += 1
			break
	return res
for _ in range(readInt()):
	n = readInt()
	ar = intList()
	print(solve())