#include <cstdio>

const int NMAX = 100010;
const int POW = 18;

int N, T;
int v[NMAX];

inline int cautbin01 (int X) {
    int i, pas = 1<<POW;
    for (i = 0; pas; pas >>= 1) {
        if (i + pas <= N && v[i + pas] <= X) {
            i += pas;
        }
    }

    return i;
}

inline int cautbin2 (int X) {
    int i, pas = 1<<POW;
    for (i = 0; pas; pas >>= 1) {
        if (i + pas <= N && v[i + pas] < X) {
            i += pas;
        }
    }

    return i;
}

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

    scanf ("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf ("%d", &v[i]);
    }

    scanf ("%d", &T);
    while (T--) {
        int tip, X;
        scanf ("%d%d", &tip, &X);

        int pos;
        switch (tip) {
            case 0: pos = cautbin01 (X);
                    if (v[pos] == X) {
                        printf ("%d\n", pos);
                    }
                    else {
                        printf ("-1\n");
                    }
                    break;

            case 1: pos = cautbin01 (X);
                    printf ("%d\n", pos);
                    break;

            case 2: pos = cautbin2 (X);
                    printf ("%d\n", pos + 1);
                    break;
        }
    }

    return 0;
}