#include <fstream>
#include <cmath>

using namespace std;

int caut_bin0(int *v, int n, int nr_cautat) {
    int p2 = (int) log2(n);
    int poz = 0;
    for (int x = 1 << p2; x > 0; x = x >> 1) {
        if (poz + x <= n && v[poz + x] <= nr_cautat) {
            poz += x;
        }
    }
    if (v[poz] == nr_cautat) {
        return poz;
    } else {
        return -1;
    }

}

int caut_bin1(int *v, int n, int nr_cautat) {
    int p2 = (int) log2(n);
    int poz = 0;
    for (int x = 1 << p2; x > 0; x = x >> 1) {
        if (poz + x <= n && v[poz + x] <= nr_cautat) {
            poz += x;
        }
    }

    return poz;
}

int caut_bin2(int *v, int n, int nr_cautat) {
    int p2 = (int) log2(n);
    int poz = 0;
    for (int x = 1 << p2; x > 0; x = x >> 1) {
        if (poz + x <= n && v[poz + x] < nr_cautat) {
            poz += x;
        }
    }
    return poz + 1;
}

int main() {
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int n, m;
    fin >> n;
    int v[n + 1];
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    fin >> m;
    for (int i = 0; i < m; i++) {
        int var, nr;
        fin >> var >> nr;
        if (var == 0)
            fout << caut_bin0(v, n, nr) << '\n';
        else if (var == 1)
            fout << caut_bin1(v, n, nr) << '\n';
        else
            fout << caut_bin2(v, n, nr) << '\n';
    }

    fin.close();

    fout.close();

    return 0;
}