#include <iostream>
#include <fstream>

using namespace std;

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

const int MAXN = 100010;

int N, logN;
int V[MAXN];

inline int BS0 (const int &val)
{
    int i = 0, step;

    for (step = logN; step; step >>= 1)
        if (i + step <= N && V[i + step] <= val)
            i += step;

    if (V[i] == val)
        return i;
    else
        return -1;
}

inline int BS1 (const int &val)
{
    int i = 0, step;

    for (step = logN; step; step >>= 1)
        if (i + step <= N && V[i + step] <= val)
            i += step;

    return i;
}

inline int BS2 (const int &val)
{
    int i = N, step;

    for (step = logN; step; step >>= 1)
        if (i - step >= 1 && V[i - step] >= val)
            i -= step;

    return i;
}

inline int BS (const int &op, const int &val)
{
    if (op == 0)
        return BS0 (val);

    if (op == 1)
        return BS1 (val);

    if (op == 2)
        return BS2 (val);
}

int main()
{
    int M, i, op, val;

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

    for (logN = 1; logN < N; logN <<= 1);

    in >> M;

    for (i = 1; i <= M; i ++){
        in >> op >> val;
        out << BS (op, val) << "\n";
    }

    return 0;
}