#include <bits/stdc++.h>

#define nrmax 100001

using namespace std;

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

int a[nrmax], N, v, M, x;

int CautareBinara0(int stanga, int dreapta, int v)
{
    int mijloc, p {-1};
    while (stanga<=dreapta)
    {
        mijloc = (stanga + dreapta) / 2;
        if (a[mijloc] <= v)
            stanga = mijloc + 1;
        else
            dreapta= mijloc - 1;
        if (a[mijloc] == v)
            p = mijloc;
    }
    return p;
}

int CautareBinara1(int stanga, int dreapta, int v)
{
    int mijloc, p {-1};
    while (stanga <= dreapta)
    {
        mijloc = (stanga + dreapta) / 2;
        if (a[mijloc] <= v)
            stanga = mijloc + 1, p = mijloc;
        else
            dreapta = mijloc - 1;
    }
    return p;
}

int CautareBinara2(int stanga, int dreapta, int v)
{
    int mijloc, p {-1};
    while (stanga <= dreapta)
    {
        mijloc = (stanga + dreapta) / 2;
        if (a[mijloc] >= v)
            dreapta = mijloc - 1, p = mijloc;
        else
            stanga = mijloc + 1;
    }
    return p;
}

int main()
{
    in >> N;
    for (int i = 1; i <= N; ++i)
        in >> a[i];
    in >> M;
    while (M--)
    {
        in >> x >> v;
        if (x == 0)
            out << CautareBinara0(1, N, v) << '\n';
        if (x == 1)
            out << CautareBinara1(1, N, v) << '\n';
        if (x == 2)
            out << CautareBinara2(1, N, v) << '\n';
    }
    return 0;
}