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: interview

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())
 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:
  print(yc)
 else:
  print(-1)


# cook your dish here
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());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())
 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
 # print(l.count(max(l)))
 a=l.count(min(l))
 b=l.count(max(l))
 if max(l)==a:
  print(b)
 else:
  print(-1)

# cook your dish here


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
 # print(l.count(max(l)))
 a=l.count(min(l))
 b=l.count(max(l))
 if max(l)==a:
  print(b)
 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-1and 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)

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 
 # print(l.count(max(l)))
 a=l.count(min(l))
 b=l.count(max(l))
 if max(l)==a:
  print(b)
 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)
  else:
   if 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]])
    #  y=len([i for i in it if i==aa[1]])
    if x==aa[1]:
     print(n-x)
    else:
     print(-1)
   else:
    print(-1)
    
  else:
   print(-1)
  


# cook your dish here
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)

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)
 # ans = max(s)
 # print(n-ans)


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)
 else:
  if 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)

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)
 else:
  if 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())):
 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')


# cook your dish here
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)
 else :
  if(len(s)== 1):
   if(s[0]==0):
    print(n)
   else :
    if(s[0]==n-1):
     print(0)
    else :
     print(-1)
  else :
   p = a.count(s[0])
   if(s[1]-s[0] != 1 ):
    print(-1)
   else :
    if(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)
 #max_number must smaller becuase if it is equal, it means one student
 #saw himself which can't happen
 #(max_number - min_number) is always 0 or 1
 if max_number < number_of_students and min_number > -1 and \
 abs(max_number - min_number) <= 1:
  #can't see himself
  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)
 #print(sorted(x),y,z)
 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
   #print(sorted(t))
   if sorted(t)==sorted(x):
    f=a-max(z)
    break
   else:
    f=-1
 else:
  f=-1
 print(f)