#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;

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

                if (vect[j] == x)
                    out << j << "\n";
                else
                    out << "-1\n";

                continue;
            }
        case 1:
            {
                for (j = 0, step = log; step; step >>= 1)
                    if (j + step <= N && vect[j + step] <= x)
                        j += step;

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

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

    in.close();
    out.close();
    return 0;
}