#include <cstdlib>
#include <cstdio>


#define nmax 100001

int N , M , op , x ;
int v[nmax] ;

int cautare_binara0 ( int stanga , int dreapta )
{
    int mid ;
    while ( stanga < dreapta )
    {
        mid = ( stanga + dreapta ) / 2 ;
        if ( v[mid] <= x ) stanga = mid + 1 ;
            else dreapta = mid ;
    }
    if ( v[stanga - 1] != x ) return -1 ;
        else return stanga - 1 ;
}

int cautare_binara1 ( int stanga , int dreapta )
{
    int mid ;
    while ( stanga < dreapta )
    {
        mid = ( stanga + dreapta ) / 2 ;
        if ( v[mid] <= x ) stanga = mid + 1 ;
            else dreapta = mid ;
    }
    return stanga - 1 ;
}


int cautare_binara2 ( int stanga , int dreapta )
{
    int mid ;
    while ( stanga < dreapta )
    {
        mid = ( stanga + dreapta ) / 2 ;
        if ( x <= v[mid] ) dreapta = mid ;
            else stanga = mid + 1 ;
    }

    return stanga ;
}



int main ()
{
    FILE *fin , *fout ;

    fin = fopen ( "cautbin.in" , "rt" ) ;
    fout = fopen ( "cautin.out" , "wt" ) ;
    freopen ( "cautbin.out" , "wt" , stdout ) ;

    fscanf ( fin , "%d" , &N ) ;
    for ( int i = 1 ; i <= N ; i++ )
        fscanf ( fin , "%d " , &v[i] ) ;

    fscanf ( fin , "%d" , &M ) ;


    for ( int i = 1 ; i <= M ; i++ )
    {
        fscanf ( fin , "%d %d " , &op , &x ) ;
       // printf ( "%d %d\n" , op , x ) ;
        if ( !op )
            {
               printf ( "%d\n" , cautare_binara0 ( 1 , N ) ) ;
               continue;
            }
        if ( op == 1 )
            {
                printf ( "%d\n" , cautare_binara1 ( 1 , N ) ) ;
            }
        if ( op == 2 )
            {
                printf ( "%d\n" , cautare_binara2 ( 1 , N ) ) ;
                continue;
            }

    }

    fclose ( fin ) ;
    fclose ( fout );

    return 0 ;


}