#include <fstream>

using namespace std;

ofstream fout("cautbin.out");


int v[100001] , N , M , intrebare , x;

void CautareBinara0()
{
    int s = 1 , f = N , mijloc , poz = -1;

    while ( s <= f  && ( poz < 0 ))
    {
        mijloc = ( s + f ) / 2;
        if ( x == v[mijloc] )
        {
            for ( int i = mijloc ; i <= N ; ++i )
                if ( v[i] == x )
                    poz = i;
                else
                    break;
        }
        else
            if ( x < v[mijloc] )
                f = mijloc - 1;
            else
                s = mijloc + 1;
    }
    fout << poz << '\n';
}

void CautareBinara1()
{
    int f = N , mijloc , poz = -1;
    while ( 1 <= f && ( poz < 0 ) )
    {
        mijloc = ( 1 + f ) / 2;
        if ( v[mijloc] <= x )
        {
            for ( int i = mijloc ; i <= N ; ++i )
                if ( v[i] <= x )
                    poz = i;
                else
                    break;
        }
        else
            f = mijloc - 1;
    }
    fout << poz << '\n';
}

void CautareBinara2()
{
    int s = 1 , mijloc , poz = -1;
    while (s <= N )
    {
        mijloc = ( s + N ) / 2;
        if ( v[mijloc] >= x )
        {
            for ( int i = mijloc ; i >= 1; --i )
                if ( v[i] >= x )
                    poz = i;
                else
                    break;
        }
        else
            s = mijloc + 1;
    }
    fout << poz << '\n';
}

int main()
{
    ifstream fin("cautbin.in");

    fin >> N; // N apoi un sir de N elemente
    for ( int i = 1 ; i <= N ; ++i )
        fin >> v[i];

    fin >> M; // M apoi M linii de 2 elemente fiecare

    for ( int i = 1 ; i <= M ; ++i )
    {
        fin >> intrebare >> x;

        switch ( intrebare )
        {
        case 1:
            CautareBinara1();
            break;
        case 2:
            CautareBinara2();
            break;
        default:
            CautareBinara0();
        }
    }
    return 0;
}