#include <stdio.h>
#include <stdlib.h>

int binsearch2(int *data, int inf, int sup, int x) {
    if (inf == sup)
        return inf;
    if ((inf + 1) == sup)
        return data[sup] == x ? sup : inf;

    int middle = inf + (sup - inf) / 2;

    if (data[middle] == x)
        return binsearch2(data, middle, sup, x);
    return binsearch2(data, inf, middle, x);
}

int binsearch(int *data, int inf, int sup, int x) {
    if (inf == sup)
        return data[inf] == x ? inf : -1;

    int middle = inf + (sup - inf) / 2;

    if (data[middle] > x) {
        return binsearch(data, inf, middle, x);
    }
    else if (data[middle] < x) {
        return binsearch(data, middle, sup, x);
    }
    return binsearch2(data, middle, sup, x);
}

int binsearchle(int *data, int inf, int sup, int x) {
    if (inf == sup)
        return data[inf] <= x ? inf : -1;
    if ((inf + 1) == sup) {
        if (data[sup] <= x)
            return sup;
        else if (data[inf] <= x)
            return inf;
        return -1;
    }

    int middle = inf + (sup - inf) / 2;

    if (data[middle] <= x) {
        if (data[middle + 1] <= x)
            return binsearchle(data, middle + 1, sup, x);
        return middle;
    }

    if (data[middle] > x)
        return binsearchle(data, inf, middle, x);
    return binsearchle(data, middle, sup, x);
}

int binsearchge(int *data, int inf, int sup, int x) {
    if (inf == sup)
        return data[inf] <= x ? inf : -1;
    if ((inf + 1) == sup) {
        if (data[inf] >= x)
            return inf;
        else if (data[sup] >= x)
            return sup;
        return -1;
    }

    int middle = inf + (sup - inf) / 2;

    if (data[middle] >= x) {
        if (data[middle - 1] >= x)
            return binsearchge(data, inf, middle - 1, x);
        return middle;
    }

    if (data[middle] > x)
        return binsearchge(data, inf, middle, x);
    return binsearchge(data, middle, sup, x);
}

int main(int argc, char **argv) {
    int N, M;
    int *data, i, result, q, x;
    freopen("cautbin.in", "r", stdin);
    //freopen("cautbin.out", "w", stdout);

    scanf("%d", &N);
    data = (int *)malloc(N * sizeof(int));
    for (i = 0; i < N; i++) {
        scanf("%d", &data[i]);
    }

    scanf("%d", &M);

    for (i = 0; i < M; i++) {
        scanf("%d %d", &q, &x);
        if (q == 0)
            result = binsearch(data, 0, N - 1, x);
        else if (q == 1)
            result = binsearchle(data, 0, N - 1, x);
        else
            result = binsearchge(data, 0, N - 1, x);

        if (result != -1)
            ++result;
        printf("%d\n", result);
    }


    return 0;
}