#include<fstream>

using namespace std;

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

int n, v[ 100001 ], i, q, tp, val;

int bsrc0( int p, int u, int nr ){

    int m;

    while( p <= u ){
        m = ( u + p ) / 2;
        if( v[ m ] <= nr )
            p = m + 1;
        else
            u = m - 1;
    }
    m = ( p + u ) / 2;
    if( v[ m ] > nr ) m--;
    if( v[ m ] == nr )
        return m;
    else return -1;
}
int bsrc1( int p, int u, int nr ){

    int m;

    while( p < u ){
        m = ( p + u ) / 2;
        if( v[ m ] <= nr )
            p = m + 1;
        else
            u = m;
    }
    m = ( u + p ) / 2;
    if( v[ m ] > nr )m--;
    return m;
}
int bsrc2( int p, int u, int nr ){

    int m;

    while( p < u ){
        m = ( u + p ) / 2;
        if( v[ m ] >= nr )
            u = m;
        else
            p = m + 1;
    }
    m = ( u + p ) / 2;
    if( v[ m ] < nr )m++;
    return m;
}
int main(){
    f >> n;
    for( i = 1; i <= n; ++i )
        f >> v[ i ];
    f >> q;
    for( i = 1; i <= q; ++i ){
        f >> tp >> val;
        if( tp == 0 ) g << bsrc0( 1, n, val ) << '\n';
        if( tp == 1 ) g << bsrc1( 1, n, val ) << '\n';
        if( tp == 2 ) g << bsrc2( 1, n, val ) << '\n';
     }
    return 0;
}