#include <fstream>

using namespace std;

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

int v[100001];

int dr, st, med, n, x;

int cautbin ()
{
    dr = n;
    st = 1;
    int gasit = -1;
    while (st <= dr)
    {
        med = (st + dr) / 2;
        if (v[med] <= x)
            st = med + 1;
        else
            dr = med - 1;
    }
    if (v[dr] == x)
        return dr;
    else
        return -1;
}

int cautbin1 ()
{
    dr = n;
    st = 1;
    while (st <= dr)
    {
        med = (st + dr) / 2;
        if (v[med] <= x)
            st = med + 1;
        else
            dr = med - 1;
    }
    return dr;
}

int cautbin2 ()
{
    dr = n;
    st = 1;
    while (st <= dr)
    {
        med = (st + dr) / 2;
        if (v[med] >= x)
            dr = med - 1;
        else
            st = med + 1;
    }
    return st;
}
int main()
{
    int m, intr, j, i;
    in >> n;
    for (i = 1; i <= n; i++)
        in >> v[i];

    in >> m;
    for (i = 1; i <= m; i++)
    {
        in >> intr >> x;
        if (intr == 0)
            out << cautbin() << '\n';
        if (intr == 1)
            out << cautbin1() << '\n';
        if (intr == 2)
            out << cautbin2() << '\n';
    }
    return 0;
}