#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]) {
            dr = m-1;
        }
        else if (x >= v[m]) {
            st = 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]) {
            dr = m-1;
        }
        else if (x >= v[m]) {
            st = m+1;
        }
    }
    m = jum(st, dr);

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

    return -1;
}

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

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

    return -1;
}

int main() {
    int N, O, st, dr, m, 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);
    for (; O > 0; --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;
}