#include <iostream>
#include <fstream>

using namespace std;

const int NMAX = 100001;

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

int v[NMAX];
int N, Q;
int task, x;

int BS( int lf, int rg, int val ){
    if( lf > rg ) return -1;

    int mid = lf + ( rg - lf ) / 2;

    if( v[mid] == x )
        return max( mid, BS( mid+1, rg, val ));

    if( v[mid] > x )
        return BS( lf, mid-1, val );
    else return BS( mid+1, rg, val );

}

int LB( int lf, int rg, int val ){
    if( lf > rg ) return -1;

    int mid = lf  + (rg-lf)/2;

    if( v[mid] <= x )
        return max( mid, LB(mid+1, rg, val));
    else return LB( lf, mid-1, val);
}

int UB( int lf, int rg, int val ){
    if( lf > rg ) return N+1;

    int mid = lf + (rg-lf)/2;

    if( v[mid] >= x )
        return min( mid, UB(lf, mid-1, val));
    else return UB( mid+1, rg, val);
}

int main()
{
    fin >> N;

    for( int i = 1; i <= N; ++i )
        fin >> v[i];

    fin >> Q;

    for( int i = 1; i <= Q; ++i ){
        fin >> task >> x;

        if( task == 0 )
            fout << BS( 1, N, x ) << '\n';
        if( task == 1 )
            fout << LB( 1, N, x ) << '\n';
        if( task == 2 )
            fout << UB( 1, N, x ) << '\n';
    }


    return 0;
}