#include <fstream>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

#define NMAX 100005

int v[NMAX];

int cb(int n, int x) {
    int st = 0, dr = n + 1;
    while (dr - st > 1) {
        int mij = (st + dr) / 2;
        if (v[mij] <= x) {
            st = mij;
        } else {
            dr = mij;
        }
    }
    if (st == 0 || v[st] != x) {
        return -1;
    }
    return st;
}

int cb1(int n, int x) {
    int st = 0, dr = n + 1;
    while (dr - st > 1) {
        int mij = (st + dr) / 2;
        if (v[mij] <= x) {
            st = mij;
        } else {
            dr = mij;
        }
    }
    return st;
}

int cb2(int n, int x) {
    int st = 0, dr = n + 1;
    while (dr - st > 1) {
        int mij = (st + dr) / 2;
        if (v[mij] < x) {
            st = mij;
        } else {
            dr = mij;
        }
    }
    return dr;
}

int main() {
    int n;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }

    int m;
    fin >> m;
    while (m--) {
        int op, x;
        fin >> op >> x;

        if (op == 0) {
            fout << cb(n, x) << '\n';
        } else if (op == 1) {
            fout << cb1(n, x) << '\n';
        } else {
            fout << cb2(n, x) << '\n';
        }
    }
    return 0;
}