#include <fstream>
using namespace std;

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

int N, A[100001];

int binsrc(int val, bool ok = false)
{
    int i, step;
    for (step = 1; step < N; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step <= N && A[i + step] <= val)
            i += step;
    if (A[i] != val && ok) return -1;
    return i;
}

int binsrc2(int val)
{
    int i, step;
    for (step = 1; step < N; step <<= 1);
    for (i = N; step; step >>= 1)
        if (i - step > 0 && A[i - step] >= val)
            i -= step;
    return i;
}

int main()
{
    int m, c, x; in >> N;
    for (int i = 1; i <= N; i++) in >> A[i];
    in >> m;
    for (int i = 1; i <= m; i++)
    {
        in >> c >> x;
        switch(c)
        {
            case 0: out << binsrc(x, true) << '\n'; break;
            case 1: out << binsrc(x) << '\n'; break;
            case 2: out << binsrc2(x) << '\n'; break;
        }
    }
    return 0;
}