#include <fstream>

using namespace std;

int N, M;
int v[100005];

int B_Search_0 (int val) {
    int i, step = 1 << 17;
    for (i = 0; step; step >>= 1)
    {
        if (i + step < N && v[i + step] <= val) i += step;
    }
    if (v[i] == val) return i + 1;
    return -1;
}

int B_Search_1 (int val) {
    int i, step = 1 << 17;
    for (i = 0; step; step >>= 1)
    {
        if (i + step < N && v[i + step] <= val) i += step;
    }
    return i + 1;
}

int B_Search_2 (int val) {
    int i, step = 1 << 17;
    for (i = N - 1; step; step >>= 1)
    {
        if (i - step >= 0 && v[i - step] >= val) i -= step;
    }
    return i + 1;
}

int main () {
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");
    fin >> N;
    for (int i = 0; i < N; i++)
    {
        fin >> v[i];
    }
    fin >> M;
    for (int i = 0, a, b; i < M; i++)
    {
        fin >> a >> b;
        if (!a) fout << B_Search_0 (b) << "\n";
        else if (a == 1) fout << B_Search_1 (b) << "\n";
        else fout << B_Search_2 (b) << "\n";
    }
    fin.close ();
    fout.close ();
    return 0;
}