#include <cstdio>
using namespace std;

inline int jum(int a, int b) {
    return a + (b - a) / 2;
}

int v[100001];

int b0(int st, int dr, int x) {
    int m;
    while (dr >= st) {
        m = jum(st, dr);
        if (x >= v[m])
            st = m+1;
        else
            dr = m-1;
    }
    m = jum(st, dr);

    if (x < v[m]) m--;
    if (x == v[m])
        return m;
    return -1;
}

int b1(int st, int dr, int x) {
    int m;
    while (dr >= st) {
        m = jum(st, dr);
        if (x >= v[m]) {
            st = m+1;
        } else {
            dr = m-1;
        }
    }
    m = jum(st, dr);

    if (x < v[m])
        m--;
    return m;
}

int b2(int st, int dr, int x) {
    int m;
    while (dr >= st) {
        m = jum(st, dr);
        if (x > v[m]) {
            st = m+1;
        } else {
            dr = m-1;
        }

    }
    m = jum(st, dr);

    if (x > v[m])
        m++;
    return m;
}

int main() {
    int N, O, i, x;

    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", &O);
    while (O--) {
        scanf("%d%d", &i, &x);
        if (i == 0) { x = b0(1, N, x);}
        else if(i == 1) { x = b1(1, N, x);}
        else if(i == 2) { x = b2(1, N, x);}
        printf("%d\n", x);
    }

    return 0;
}