#include <iostream>
#include <fstream>


using namespace std;

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

int caut_bin0(int f, int l, int val, int v[]) {
    int m, poz = 0;

    while (f <= l) {
        m = f + (l - f) / 2;
        if (v[m] <= val)
           f = m + 1;
        else
            l = m - 1;
        if (v[m] == val)
            poz = m;
    }
    if (poz == 0)
        return -1;
    else
        return poz;
}

int caut_bin1(int f, int l, int val, int v[]) {
    int m, poz = 0;

    while (f <= l) {
        m = f + (l - f) / 2;
        if (v[m] <= val)
           f = m + 1;
        else
            l = m - 1;
        if (v[m] == val)
            poz = m;
    }
    if (poz == 0)
        return l;
    else
        return poz;
}

int caut_bin2(int f, int l, int val, int v[]) {
    int m, poz = 0;

    while (f <= l) {
        m = f + (l - f) / 2;
        if (v[m] < val)
           f = m + 1;
        else
            l = m - 1;
        if (v[m] == val)
            poz = m;
    }
    if (poz == 0)
        return f;
    else
        return poz;

}
int main()
{
    int N, M, v[100002], q, x;
    fin >> N;

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

    fin >> M;

    while (M) {
        fin >> q >> x;
        if (q == 0)
           fout << caut_bin0(1, N, x, v) << '\n';
        if (q == 1)
           fout << caut_bin1(1, N, x, v) << '\n';
        if (q == 2)
            fout << caut_bin2(1, N, x, v) << '\n';
        M--;
    }

    fin.close();
    fout.close();
}