#include <fstream>

using namespace std;

const int NMax = 100010;
int a[NMax], N, M;

int BS0(int st, int dr, const int x)
{
    int ret = -1;
    while (st <= dr)
    {
        int mij = (st+dr) >> 1;
        if (x == a[mij])
            ret = mij, st = mij + 1;
        else
            if (x < a[mij])
                dr = mij - 1;
            else
                st = mij + 1;
    }
    return ret;
}

int BS1(int st, int dr, const int x)
{
    int ret;
    while (st <= dr)
    {
        int mij = (st+dr) >> 1;
        if (a[mij] <= x)
        {
            ret = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return ret;
}

int BS2(int st, int dr, const int x)
{
    int ret;
    while (st <= dr)
    {
        int mij = (st+dr) >> 1;
        if (a[mij] >= x)
        {
            ret = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    return ret;
}

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f >> N;
    for (int i = 1; i <= N; ++ i)
        f >> a[i];
    f >> M;
    while (M -- )
    {
        int op, x; f >> op >> x;
        switch(op)
        {
            case 0:
            g << BS0(1, N, x) << "\n";
            break;
            case 1:
            g << BS1(1, N, x) << "\n";
            break;
            case 2:
            g << BS2(1, N, x) << "\n";
            break;
        }
    }
    f.close();
    g.close();
    return 0;
}