#include<fstream>

using namespace std;

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

const int nmax = 100000;
int sol, n2, n;
int v[ nmax + 1 ];

void solve_0( int x ) {
    sol = 1;
    for( int step = n2; step > 0; step=step>>1 ) {
        if ( sol + step <= n && v[ sol + step ] <= x ) {
            sol += step;
        }
    }
    if ( v[ sol ] != x ) {
        sol = -1;
    }
} void solve_1( int x ) {
    sol = 1;
    for( int step = n2; step > 0; step=step>>1 ) {
        if ( sol + step <= n && v[ sol + step ] <= x ) {
            sol += step;
        }
    }
} void solve_2( int x ) {
    sol = n;
    for( int step = n2; step > 0; step=step>>1 ) {
        if ( sol - step >= 1 && v[ sol - step ] >= x ) {
            sol -= step;
        }
    }
}
int main()
{
    int x, t, m;
    fin>>n;
    for( int i = 1; i <= n; ++ i ) {
        fin>>v[i];
    }
    for( n2 = 1; n2 * 2 <= n; n2=n2<<1 ) {
    }
    fin>>m;
    for( int i = 0; i < m; ++ i ) {
        fin>>t>>x;
        switch( t ) {
            case 0 : solve_0( x ); break;
            case 1 : solve_1( x ); break;
            default : solve_2( x ); break;
        }
        fout<<sol<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}