CLPNT.java

import java.io.IOException;
import java.io.InputStream;
import java.util.*;
 
class Solution {
    static int n;
    static int arr[];
    static int binary(int z){
        if(z<arr[0])
            return 0;
        int l=0,r=n-1;
        while(l<=r){
            if(l==r)
                return l+1;
            if(l+1==r){
                if(arr[r]<z)
                    return r+1;
                return l+1;
            }
            int m=(l+r)/2;
            if(arr[m]<z)
                l=m;
            else
                r=m-1;
        }
        return -1;
    }
    public static void main(String[] args) throws Exception {
        FastReader in=new FastReader(System.in);
        StringBuilder sb=new StringBuilder();
        int i,j;
        int t=in.nextInt();
        while(t-->0){
            n=in.nextInt();
            arr=new int[n];
            HashSet<Integer> set=new HashSet<>();
            for(i=0;i<n;i++){
                arr[i]=in.nextInt();
                set.add(arr[i]);
            }
            int q=in.nextInt();
            while(q-->0){
                int z=in.nextInt()+in.nextInt();
                if(set.contains(z))
                    sb.append("-1\n");
                else
                    sb.append(binary(z)).append("\n");
            }
        }
        System.out.print(sb);
    }
}
 
class FastReader {
 
    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;
 
    FastReader(InputStream is) {
        in = is;
    }
 
    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }
 
    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }
 
    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}