#include <fstream>
using namespace std;

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    int N;
    int M;
    int tip;
    int x;
    int i;
    int j;
    int log;
    int step;
    int* vect;

    in >> N;
    vect = new int[N + 1];

    for (int i = 1; i <= N; ++i)
        in >> vect[i];

    log = 1;
    while (log < N)
        log <<= 1;

    in >> M;
    for (int i = 1; i <= M; ++i)
    {
        in >> tip >> x;

        if (tip == 0 || tip == 1)
        {
            for (j = 0, step = log; step; step >>= 1)
                if (j + step <= N && vect[j + step] <= x)
                    j += step;

            if (tip == 1)
                out << j << "\n";
            else
                if (vect[j] == x)
                    out << j << "\n";
                else
                    out << "-1\n";
        }
        else
        {
            for (j = N, step = log; step; step >>= 1)
                if (j - step > 0 && vect[j - step] >= x)
                    j -= step;

            out << j << "\n";
        }
    }

    delete[] vect;
    in.close();
    out.close();

    return 0;
}