It's year 2018 and it's Christmas time! Before going for vacations, students of Hogwarts School of Witchcraft and Wizardry had their end semester exams.
$N$ students attended the semester exam. Once the exam was over, their results were displayed as either "Pass" or "Fail" behind their magic jacket which they wore. A student cannot see his/her result but can see everyone else's results. Each of $N$ students count the number of passed students they can see.
Given the number of "Pass" verdicts that each of the $N$ students counted, we have to figure out conclusively, the number of students who failed, or report that there is some inconsistency or that we cannot be sure.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- The first line of each test case will contain $N$, representing the number of students who attended the exam.
- Next line contains  $N$ spaced integers representing the number of "Pass" counted by each of the $N$ students.

-----Output:-----
- For each test case, output the answer in a single line. 
- If the counts reported by the students are not consistent with each other or if it's not possible to predict the number of failed students from the given input, then print -1.

-----Constraints-----
- $1 \leq T \leq 50$
- $1 \leq N \leq 10^{5}$
- $0 \leq$ Count given by each Student $\leq 10^{5}$

-----Sample Input:-----
1
4
3 2 2 2

-----Sample Output:-----
1

-----EXPLANATION:-----
There are 4 students, and they counted the number of passed students as 3,2,2,2. The first student can see that all others have passed, and all other students can see only 2 students who have passed. Hence, the first student must have failed, and others have all passed. Hence, the answer is 1.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	if n == 1 or len(s) > 2:
		print(-1)
		continue
	if len(s) == 1:
		x = s.pop()
		if x == 0:
			print(n)
		elif x == n - 1:
			print(0)
		else:
			print(-1)
		continue
	(x, y) = sorted(s)
	(xc, yc) = (a.count(x), a.count(y))
	if xc == y and xc == x + 1:
		print(yc)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	if n == 1:
		print(-1)
		continue
	if len(set(l)) == 1:
		if l[0] == 0:
			print(n)
		elif l[0] == n - 1:
			print(0)
		else:
			print(-1)
		continue
	if len(set(l)) > 2 or max(l) - min(l) > 1:
		print(-1)
		continue
	(a, b) = (l.count(min(l)), l.count(max(l)))
	print(b) if max(l) == a else print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	if len(d) > 2:
		print(-1)
	elif len(d) == 1:
		for i in d:
			if i == n - 1 and d[i] == n:
				print(0)
			elif i == 0 and d[i] == n:
				print(n)
			else:
				print(-1)
	else:
		k = max(d.keys())
		if d.get(k - 1, 0) == k and d[k] == n - k:
			print(n - k)
		else:
			print(-1)


t = int(input())
for o in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(set(a))
	b.sort()
	if n == 1:
		print(-1)
		continue
	if len(b) > 2:
		print(-1)
		continue
	if len(b) == 1:
		if b[0] == n - 1:
			print(0)
		elif b[0] == 0:
			print(n)
		else:
			print(-1)
		continue
	pa = a.count(b[0])
	fa = a.count(b[1])
	if pa != b[1] or b[1] - b[0] != 1:
		print(-1)
		continue
	print(n - pa)


t = int(input())
for _ in range(t):
	n = int(input())
	it = list(map(int, input().split()))
	x = [i for i in it if i >= n]
	if n == 1:
		print(-1)
		continue
	if len(x) > 0:
		print(-1)
		continue
	if it.count(0) == n:
		print(n)
		continue
	if n - 1 in it:
		if it == [n - 1] * n:
			print(0)
		elif it.count(n - 2) == n - 1:
			print(1)
		else:
			print(-1)
	else:
		aa = list(set(it))
		if len(aa) == 2:
			aa.sort()
			if aa[1] - aa[0] == 1:
				x = len([i for i in it if i == aa[0]])
				if x == aa[1]:
					print(n - x)
				else:
					print(-1)
			else:
				print(-1)
		else:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = list(set(a))
	if n == 1:
		print(-1)
	elif len(x) > 2:
		print(-1)
	elif len(x) == 1:
		if x[0] == n - 1:
			print(0)
		elif x[0] == 0:
			print(n)
		else:
			print(-1)
	else:
		p = max(x)
		f = a.count(p)
		if p == a.count(min(x)):
			print(f)
		else:
			print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(-1)
		continue
	s = list(set(a))
	if len(s) > 2:
		print(-1)
		continue
	if len(s) == 1:
		if s[0] == n - 1:
			print(0)
		elif s[0] == 0:
			print(n)
		else:
			print(-1)
		continue
	x = a.count(max(s))
	y = max(s)
	if y == a.count(min(s)):
		print(x)
	else:
		print(-1)


import sys
input = sys.stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	ls = list(map(int, input().strip().split()))
	ls.sort()
	if abs(ls[-1] - ls[0]) > 1:
		print(-1)
	elif len(set(ls)) == 1:
		if ls[0] == 0:
			print(len(ls))
		elif len(ls) == ls[0] + 1:
			print(0)
		else:
			print(-1)
	else:
		i = n - 1
		cnt = 0
		while ls[i] == ls[n - 1]:
			i -= 1
			cnt += 1
		passed = n - cnt
		if ls[0] != passed - 1:
			print(-1)
		else:
			print(cnt)


for _ in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	d = {}
	for i in m:
		try:
			d[i]
		except:
			d[i] = 1
		else:
			d[i] += 1
	(mam, mim) = (max(m), min(m))
	pc = list(d.items())
	if len(pc) == 2 and mam == mim + 1:
		if d[mam] + d[mim] == n and mim == d[mim] - 1:
			ans = d[mam]
		else:
			ans = -1
	elif len(pc) == 1:
		if mam == n - 1:
			ans = 0
		elif mam == 0:
			ans = n
		else:
			ans = -1
	else:
		ans = -1
	print(ans)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = max(b)
	if a == 1:
		print('-1')
	else:
		l = set(b)
		if b == [c] * a:
			if c == 0:
				print(a)
			elif c == a - 1:
				print('0')
			else:
				print('-1')
		elif len(l) == 2:
			if b.count(c) == a - c and b.count(c - 1) == c:
				print(a - c)
			else:
				print('-1')
		else:
			print('-1')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	s = []
	s.append(a[0])
	for i in range(1, n):
		if a[i] != a[i - 1]:
			s.append(a[i])
	if len(s) > 2:
		print(-1)
	elif len(s) == 1:
		if s[0] == 0:
			print(n)
		elif s[0] == n - 1:
			print(0)
		else:
			print(-1)
	else:
		p = a.count(s[0])
		if s[1] - s[0] != 1:
			print(-1)
		elif p == s[0] + 1:
			print(n - p)
		else:
			print(-1)


t = int(input())
for i in range(t):
	number_of_students = int(input())
	list_of_numbers = list(map(int, input().split(' ')))
	max_number = max(list_of_numbers)
	min_number = min(list_of_numbers)
	if max_number < number_of_students and min_number > -1 and (abs(max_number - min_number) <= 1):
		sum_of_values = sum(list_of_numbers)
		if number_of_students == 1:
			print(-1)
		elif sum_of_values % (number_of_students - 1) != 0:
			print(-1)
		else:
			print(number_of_students - sum_of_values // (number_of_students - 1))
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	jhol = 0
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	if len(d) > 2:
		jhol = 1
		print(-1)
	elif len(d) == 1:
		b = list(set(a))
		x = b[0]
		if d[x] == n and x == n - 1:
			print(0)
		elif x == 0:
			print(n)
		else:
			print(-1)
	else:
		b = set(a)
		x = d[max(b)]
		y = max(b)
		if y == d[min(b)]:
			print(x)
		else:
			print(-1)


for _ in range(int(input())):
	a = int(input())
	x = list(map(int, input().split()))
	y = set(x)
	z = list((k for k in y))
	if len(z) == 1:
		if z[0] == 0:
			f = a
		elif z[0] == a - 1:
			f = 0
		else:
			f = -1
	elif len(y) == 2:
		for r in range(0, a + 1):
			t = [r] * (a - r) + [r - 1] * r
			if sorted(t) == sorted(x):
				f = a - max(z)
				break
			else:
				f = -1
	else:
		f = -1
	print(f)