#include <fstream>

using namespace std ;

const int NR = 100005 ;

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

int binary_search0 ( int val , int n , int v [] )
{
    int step , i ;
    for ( step = 1 ; step < n ; step <<= 1 ) ;
    
    for ( i = 0 ; step ; step >>= 1 )
    if ( i + step < n && v [ step + i ] <= val )
    i += step ;
    if ( v [ i ] != val )   return -1 ;
    return i ;
}

int binary_search1 ( int val , int n , int v [] )
{
    int step , i ;
    for ( step = 1 ; step < n ; step <<= 1 ) ;
    
    for ( i = 0 ; step ; step >>= 1 )
    if ( i + step < n && v [ step + i ] <= val )
    i += step ;
    
    return i ;
}

int binary_search2 ( int val , int n , int v [] )
{
    int step , i ;
    for ( step = 1 ; step < n ; step <<= 1 ) ;
    
    for ( i = 0 ; step ; step >>= 1 )
    if ( i + step < n && v [ step + i ] <= val )
    i += step ;
    
    return i + 1 ;
}

int main ()
{
    int n , q ; f >> n ;
    int v [ n + 1 ] ;
    for ( int i = 1 ; i <= n ; ++ i )   f >> v [ i ] ;
    f >> q ;
    while ( q -- )
    {
        int type , value ;
        f >> type >> value ;
        if ( type == 0 ) g << binary_search0 ( value , n , v ) << "\n" ;
        if ( type == 1 ) g << binary_search1 ( value , n , v ) << "\n" ;
        if ( type == 2 ) g << min ( binary_search2 ( value  , n , v ) , binary_search2 ( value - 1 , n , v ) ) << "\n" ;
        
    }
}