import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

    private static int x;
    private static int[] array;

    public static void main(String[] args) throws IOException {

        Scanner is = new Scanner(new FileInputStream("cautbin.in"));
        PrintWriter os = new PrintWriter("cautbin.out");

        int n = is.nextInt();
        array = new int[n];
        for(int i = 0; i < n; ++i) {
            array[i] = is.nextInt();
        }
        
        int q = is.nextInt();
        int type;
        for(int i = 0; i < q; ++i) {
            type = is.nextInt();
            x = is.nextInt();
            switch(type) {
                case 0:
                    os.println(binarySearch1(0, n-1));
                    break;
                case 1:
                    os.println(binarySearch2(0, n-1));
                    break;
                case 2:
                    os.println(binarySearch3(0, n-1));
                    break;
            }
        }

        is.close();
        os.close();
    }

    // Finds the highest position of an element equal to x
    private static int binarySearch1(int left, int right) {
        int middle = left + (right - left) / 2;
        int answer = -2;

        while(left <= right) {

            if (x == array[middle]) {
                answer = middle;
                left = middle + 1;
            } else if (x < array[middle]) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }

            middle = left + (right - left) / 2;
        }

        return answer + 1;
    }

    // Finds the highest position of an element less than or equal to x
    private static int binarySearch2(int left, int right) {
        int middle = left + (right - left) / 2;
        int answer = -2;

        while(left <= right) {
            if(array[middle] <= x) {
                answer = middle;
                left = middle + 1;
            } else {
                right = middle - 1;
            }
            middle = left + (right - left) / 2;
        }

        return answer + 1;
    }

    // Finds the lowest position of an element greater than or equal to x
    private static int binarySearch3(int left, int right) {
        int middle = left + (right - left) / 2;
        int answer = -2;

        while(left <= right) {
            if (array[middle] >= x) {
                answer = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }

            middle = left + (right - left) / 2;
        }

        return answer + 1;
    }
}