#include <cstdio>
using namespace std;

int v[100001];

int BSL(int st, int dr, int x) {
    int med, last = -1;
    while (st <= dr) {
        med = (st + dr) / 2;
        if (x <= v[med]) {
            last = med;
            dr = med - 1;
        } else
            st = med + 1;
    }
    return last;
}

int bsr(int st, int dr, int x) {
    int med, last = -1;
    while (st <= dr) {
        med = (st + dr) / 2;
        if (x >= v[med]) {
            last = med;
            st = med + 1;
        } else
            dr = med - 1;
    }
    return last;
}

int bs(int st, int dr, int x) {
    int med;
    while (st <= dr) {
        med = (st + dr) / 2;
        if (v[med] == x)
            return 1;
        else if (v[med] > x)
            dr = med - 1;
        else
            st = med + 1;
    }
    return 0;
}

int main() {
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    int n, i, m, q, a;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%d", &v[i]);
    scanf("%d", &m);
    for (i = 1; i <= m; i++) {
        scanf("%d%d", &q, &a);
        if (q == 0) {
            if (bs(1, n, a))
                printf("%d\n", bsr(1, n, a));
            else
                printf("-1\n");
        } else if (q == 1)
            printf("%d\n", bsr(1, n, a));
        else
            printf("%d\n", BSL(1, n, a));
    }
    return 0;
}