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

int data[100001];

int binsearch(int inf, int sup, int x) {
    if (inf > sup) return sup;

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

    if (data[middle] > x) {
        return binsearch(inf, middle - 1, x);
    }
    return binsearch(middle + 1, sup, x);
}

int binsearchle(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(middle + 1, sup, x);
        return middle;
    }

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

int binsearchge(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(inf, middle - 1, x);
        return middle;
    }

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

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

    scanf("%d", &N);
    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(0, N - 1, x);
        else if (q == 1)
            result = binsearchle(0, N - 1, x);
        else
            result = binsearchge(0, N - 1, x);

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


    return 0;
}