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

public class Main {

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

        os.close();
    }

    // Finds the highest position of an element equal to x
    private static int binarySearch1(int x) {
        int left = 0;
        int right = n-1;
        int middle = (left + right) / 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) / 2;
        }

        return answer + 1;
    }

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

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

        return answer + 1;
    }

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

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

            middle = (left + right) / 2;
        }

        return answer + 1;
    }
}