#include <stdio.h>

#define MAXN 1000005

int v[MAXN];

int main() {
    FILE *fin,*fout;
    int st, dr, c, x, n, i, q, rez, mij;
    fin=fopen("cautbin.in", "r");
    fscanf(fin, "%d", &n);
     
    for (i = 0; i < n; i++) {
        fscanf(fin, "%d", &v[i]);
    }
    fscanf(fin, "%d", &q);
    fout=fopen("cautbin.out", "w");
    while (q--) {
        fscanf(fin, "%d %d", &c, &x);

        if (c == 0) {
            st = 0;
            dr = n - 1;
             rez = -2;

            while (st <= dr) {
                mij = st + (dr - st) / 2;

                if (v[mij] < x)
                    st = mij + 1;
                else if (v[mij] == x) {
                    rez = mij;
                    st = mij + 1;
                } else
                    dr = mij - 1;
            }

            fprintf(fout, "%d\n", (rez == -2 ? -1 : rez + 1));
        }

        else if (c == 1) {
            st = 0;
            dr = n - 1;
            rez = -2;

            while (st <= dr) {
                int mij = st + (dr - st) / 2;

                if (v[mij] <= x) {
                    rez = mij;
                    st = mij + 1;
                } else
                    dr = mij - 1;
            }

            fprintf(fout, "%d\n", (rez == -2 ? -1 : rez + 1));
        }

        else if (c == 2) {
            st = 0;
            dr = n - 1;
             rez = -2;

            while (st <= dr) {
                 mij = st + (dr - st) / 2;

                if (v[mij] >= x) {
                    rez = mij;
                    dr = mij - 1;
                } else
                    st = mij + 1;
            }

            fprintf(fout, "%d\n", (rez == -2 ? -1 : rez + 1));
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}