description: Paprika loves permutations. She has an array a_1, a_2, ..., a_n. She wants to make the array a permutation of integers 1 to n.
  
  In order to achieve this goal, she can perform operations on the array. In each operation she can choose two integers i (1 ≤ i ≤ n) and x (x > 0), then perform a_i := a_i mod x (that is, replace a_i by the remainder of a_i divided by x). In different operations, the chosen i and x can be different.
  
  Determine the minimum number of operations needed to make the array a permutation of integers 1 to n. If it is impossible, output -1.
  
  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 a single integer t (1 ≤ t ≤ 10^4) — the number of test cases. Description of the test cases follows.
  
  The first line of each test case contains an integer n (1 ≤ n ≤ 10^5).
  
  The second line of each test case contains n integers a_1, a_2, ..., a_n. (1 ≤ a_i ≤ 10^9).
  
  It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.
  
  Output
  
  For each test case, output the minimum number of operations needed to make the array a permutation of integers 1 to n, or -1 if it is impossible.
  
  Example
  
  Input
  
  
  4
  2
  1 7
  3
  1 5 4
  4
  12345678 87654321 20211218 23571113
  9
  1 2 3 4 18 19 5 6 7
  
  
  Output
  
  
  1
  -1
  4
  2
  
  Note
  
  For the first test, the only possible sequence of operations which minimizes the number of operations is: 
  
    * Choose i=2, x=5. Perform a_2 := a_2 mod 5 = 2. 
  
  
  
  For the second test, it is impossible to obtain a permutation of integers from 1 to n.
solution: import java.io.*;
  import java.math.BigInteger;
  import java.security.SecureRandom;
  import java.util.*;
  
  public class Main {
      private static ArrayList<Integer> A = new ArrayList<>();
      public static void main(String[] args) throws Exception{
          IO io = new IO(null, null);
          for (int T = io.getNextInt(); T > 0; T--) {
              int n = io.getNextInt();
              TreeMap<Integer, Integer> TM = new TreeMap<>();
              for (int i = 0; i < n; i++) {
                  int x = io.getNextInt();
                  if (!TM.containsKey(x)) {
                      TM.put(x, 0);
                  }
                  TM.put(x, TM.get(x) + 1);
              }
              A.clear();
              TreeSet<Integer> rem = new TreeSet<>();
              for (int i = 1; i <= n; i++) {
                  if (TM.containsKey(i)) {
                      TM.put(i, TM.get(i) - 1);
                  } else {
                      rem.add(i);
                  }
              }
              for (int x : TM.keySet()) {
                  int c = TM.get(x);
                  for (;c > 0; c --) {
                      A.add(x);
                  }
              }
              int ans = 0;
              int j = 0;
              for (int x : A) {
                  int i = rem.pollFirst();
                  if (x == i) continue;
                  ans ++;
                  if(i != x%(x - i)) {
                      ans = -1;
                      break;
                  }
              }
              io.println(ans);
          }
          io.close();
      }
  }
  
  class IO{
      private BufferedReader br;
      private StringTokenizer st;
      private PrintWriter writer;
      private String inputFile,outputFile;
  
      public boolean hasMore() throws IOException {
          if(st != null && st.hasMoreTokens()) return true;
          if(br != null && br.ready()) return true;
          return false;
      }
  
      public String getNext() throws FileNotFoundException, IOException{
          while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
          return st.nextToken();
      }
  
      public String getNextLine() throws FileNotFoundException, IOException{
          return br.readLine().trim();
      }
  
      public int getNextInt() throws FileNotFoundException, IOException{
          return Integer.parseInt(getNext());
      }
      public long getNextLong() throws FileNotFoundException, IOException{
          return Long.parseLong(getNext());
      }
  
      public void print(double x,int num_digits) throws  IOException{
          writer.printf("%." + num_digits + "f" ,x);
      }
      public void println(double x,int num_digits) throws  IOException{
          writer.printf("%." + num_digits + "f\n" ,x);
      }
      public void print(Object o) throws  IOException{
          writer.print(o.toString());
      }
  
      public void println(Object o) throws  IOException{
          writer.println(o.toString());
      }
      public IO(String x,String y) throws FileNotFoundException, IOException{
          inputFile = x;
          outputFile = y;
          if(x != null) br = new BufferedReader(new FileReader(inputFile));
          else br = new BufferedReader(new InputStreamReader(System.in));
          if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
          else writer = new PrintWriter(new OutputStreamWriter(System.out));
      }
  
      protected void close() throws IOException{
          br.close();
          writer.close();
      }
      public void outputArr(Object [] A) throws IOException{
          int L = A.length;
          for (int i = 0;i < L;i++) {
              if(i > 0) writer.print(" ");
              writer.print(A[i]);
          }
          writer.print("\n");
      }
  }
  
  class pollardRho{
      private static BigInteger zero = new BigInteger("0");
      private static BigInteger one  = new BigInteger("1");
      private static BigInteger two  = new BigInteger("2");
      private static SecureRandom r = new SecureRandom();
      private static TreeMap<BigInteger, Integer> HM = new TreeMap<BigInteger, Integer>();
  
      public static TreeMap<BigInteger,Integer> factorize(BigInteger N) {
          HM.clear();
          factor(N);
          return new TreeMap<>(HM);
      }
  
      private static void factor(BigInteger N) {
          if (N.compareTo(one) == 0) return;
          if (N.isProbablePrime(20)) {
              if(!HM.containsKey(N))
                  HM.put(N, 0);
              HM.put(N, HM.get(N) + 1);
              return;
          }
          BigInteger d = rho(N);
          factor(d);
          factor(N.divide(d));
      }
  
      private static BigInteger rho(BigInteger N) {
          BigInteger d;
          BigInteger c  = new BigInteger(N.bitLength(), r);
          BigInteger p  = new BigInteger(N.bitLength(), r);
          BigInteger q = p;
  
          if (N.mod(two).compareTo(zero) == 0) return two;
  
          d = one;
          while(d.compareTo(one) == 0) {
              p  =  p.multiply(p).mod(N).add(c).mod(N);
              q = q.multiply(q).mod(N).add(c).mod(N);
              q = q.multiply(q).mod(N).add(c).mod(N);
              d = p.subtract(q).gcd(N);
          }
          return d;
      }
  }
  