#include <stdio.h>

int binary_search_0(int* arr, int size, int target) {
    int low = 0;
    int high = size - 1;

    int result = -1;
    while (low < high) {
        int middle = low + (high - low) / 2;

        if (target == arr[middle]) {
            result = middle;
            low++;
        } else if (target < arr[middle]) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }

    return result;
}

int binary_search_1(int* arr, int size, int target) {
    int low = 0;
    int high = size - 1;

    int result = -1;
    while (low < high) {
        int middle = low + (high - low) / 2;

        if (target >= arr[middle]) {
            result = middle;
            low++;
        } else {
            high = middle - 1;
        }
    }

    return result;
}

int binary_search_2(int* arr, int size, int target) {
    int low = 0;
    int high = size - 1;

    int result = -1;
    while (low < high) {
        int middle = low + (high - low) / 2;

        if (target <= arr[middle]) {
            result = middle;
            high--;
        } else {
            low = middle + 1;
        }
    }

    return result;
}

int main(void) {
    FILE* file_r = fopen("cautbin.in", "r");
    FILE* file_w = fopen("cautbin.out", "w");

    long arr[100000];

    int n;
    fscanf(file_r, "%d", &n);
    for (int i = 0; i < n; i++) {
        fscanf(file_r, "%d", &arr[i]);
    }

    int m;
    fscanf(file_r, "%d", &m);
    for (int i = 0; i < m; i++) {
        int question, number;
        fscanf(file_r, "%d %d", &question, &number);

        if (question == 0) {
            fprintf(file_w, "%d\n", binary_search_0(arr, n, number));
        } else if (question == 1) {
            fprintf(file_w, "%d\n", binary_search_1(arr, n, number));
        } else if (question == 2) {
            fprintf(file_w, "%d\n", binary_search_2(arr, n, number));
        }
    }

    file_r.close();
    file_w.close();

    return 0;
}