#include <fstream>

#define nMax 100008

using namespace std;

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

int v[nMax], n ,log , tp, mamaliga, pr, poz;

int caut_bin_lower(int meh)
{
    int st = 1, dr = n;

    while(st <= dr)
    {
        int mid = (st + dr) / 2;
        if(mamaliga <= v[mid])
            dr = mid - 1;
        else
            st = mid + 1;
    }

    return st;
}

int caut_bin_upper(int meh)
{

    int st = 1, dr = n;

    while(st <= dr)
    {
        int mid = (st + dr) / 2;
        if(mamaliga >= v[mid])
            st = mid + 1;
        else
            dr = mid - 1;
    }

    return dr;
}

int main()
{
    in >> n;
    for(int i = 1; i <=n; ++i)
        in >> v[i];

    for(log = 1; (1LL << log) <= n; ++log);
    --log;

    in >> pr;

    for(int i = 0; i < pr; ++i)
    {
        in >> tp >> mamaliga;
        switch(tp)
        {
            case 0:

                poz = caut_bin_upper(mamaliga);
                if(v[poz] == mamaliga)
                    out << poz << "\n";
                else
                    out << -1 << "\n";
                break;

            case 1:

                out << caut_bin_upper(mamaliga) << "\n";
                break;

            case 2:

                out << caut_bin_lower(mamaliga) << "\n";
        }
    }
}