#include <cstdio>

int v[100005], n;

int cautbin0(int x) {
    int st = 1, dr = n, m;
    while(st <= dr) {
        m = (st + dr) >> 1;
        if(v[m] == x && v[m+1] != x)
            return m;
        else if (v[m] > x)
            dr = m - 1;
        else
            st = m + 1;
    }
    return -1;
}

int cautbin1(int x) {
    int st = 1, dr = n, m;
    while(st <= dr) {
        m = (st + dr) >> 1;
        if(v[m] <= x && (v[m+1] > x || m == n))
            return m;
        else if(v[m] > x)
            dr = m - 1;
        else
            st = m + 1;
    }
}

int cautbin2(int x) {
    int st = 1, dr = n, m;
    while(st <= dr) {
        m = (st + dr) >> 1;
        if(v[m-1] < x && v[m] >= x)
            return m;
        else if(v[m] < x)
            st = m + 1;
        else
            dr = m - 1;
    }
}

int main() {
    int m, c, x, i;
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    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", &c, &x);
        if(c == 0)
            printf("%d\n", cautbin0(x));
        else if(c == 1)
            printf("%d\n", cautbin1(x));
        else
            printf("%d\n", cautbin2(x));
    }
}