#include <cstdio>
int v[100001] ;
using namespace std;
int cb0 ( int st, int dr, int val )
{
    int med ;
    while( st <= dr ) {
        med = ( st + dr ) / 2 ;
        if( v[med] <= val )
            st = med + 1 ;
        else
            dr = med - 1 ;
    }
    if( v[med] > val )
        med-- ;
    if( v[med] == val )
        return med ;
    return -1 ;
}
int cb1 ( int st, int dr, int val )
{
    int med ;
    while( st < dr ) {
        med = ( st + dr ) / 2 ;
        if( v[med] <= val )
            st = med + 1 ;
        else
            dr = med ;
    }
    if( v[med] > val )
        med--;
    return med ;
}
int cb2( int st, int dr,int val )
{
    int med ;
    while( st < dr ) {
        med =( st + dr ) / 2 ;
        if( v[med] < val )
            st = med + 1 ;
        else
            dr = med ;
    }
    if( v[med] < val )
        med++;
    return med;
}
int main()
{   freopen( "cautbin.in" , "r" , stdin ) ;
    freopen( "cautbin.out" , "w" , stdout ) ;
    int n, m, i, tip, val ;
    scanf( "%d",&n ) ;
    for( i = 1 ; i <= n ; i++ )
        scanf( "%d",&v[i] ) ;
    scanf( "%d",&m ) ;
    for( i = 0 ; i < m ; i++ ){
        scanf( "%d%d",&tip,&val ) ;
        if( tip == 0 )
            printf( "%d\n",cb0 ( 1, n, val ) ) ;
        if( tip == 1 )
            printf( "%d\n",cb1 ( 1, n, val ) );
        if( tip == 2 )
             printf( "%d\n", cb2 ( 1, n, val ) );
    }
    return 0;
}