#include <fstream>

using namespace std;

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

int v[100002], n, m, c, x;

int bs0(int y)
{
    int st = 1, dr = n, mij, gasit = 0;
    while (st <= dr && !gasit)
    {
        mij = (st + dr) / 2;
        if (v[mij] == y)
            gasit = 1;
        else
            {
                if (v[mij] > y)
                    dr = mij - 1;
                else
                    st = mij + 1;
            }
    }
    if (!gasit)
        return -1;
    while (v[mij] == y && mij <= n) ++ mij;
    return mij - 1;
}

int bs1(int y)
{
    int st = 1, dr = n, mij, gasit = 0;
    while (st <= dr && !gasit)
    {
        mij = (st + dr) / 2;
        if (v[mij] == y)
            gasit = 1;
        else
            {
                if (v[mij] > y)
                    dr = mij - 1;
                else
                    st = mij + 1;
            }
    }
    if (gasit)
    {
        while (v[mij] == y && mij <= n) ++ mij;
        return mij - 1;
    }
    st = 1, dr = n;
    while (st <= dr && !gasit)
    {
        mij = (st + dr) / 2;
        if (v[mij] > y)
            dr = mij - 1;
        else
            gasit = 1;
    }
    int z = v[mij];
    while (v[mij] == z && mij <= n) ++ mij;
    return mij - 1;
}

int bs2(int y)
{
    int st = 1, dr = n, mij, gasit = 0;
    while (st <= dr && !gasit)
    {
        mij = (st + dr) / 2;
        if (v[mij] == y)
            gasit = 1;
        else
            {
                if (v[mij] > y)
                    dr = mij - 1;
                else
                    st = mij + 1;
            }
    }
    if (gasit)
    {
        while (v[mij] == y && mij > 0) -- mij;
        return mij + 1;
    }
    st = 1, dr = n;
    while (st <= dr && !gasit)
    {
        mij = (st + dr) / 2;
        if (v[mij] > y)
            gasit = 1;
        else
            st = mij + 1;
    }
    int z = v[mij];
    while (v[mij] == z && mij > 0) -- mij;
    return mij + 1;
}

int main()
{
    F >> n;
    for (int i = 1; i <= n; ++ i)
        F >> v[i];
    F >> m;
    for (int i = 0; i < m; ++ i)
    {
        F >> c >> x;
        if (!c) G << bs0(x) << '\n';
        else if (c == 1) G << bs1(x) << '\n';
        else if (c == 2) G << bs2(x) << '\n';
    }
    return 0;
}