#include <stdio.h>
#include <stdlib.h>
int v[100011];
int c0 ( int dr, int val ) {
    int med, st ;
    st = 1 ;
    while ( st <= dr ) {
        med = (st + dr) >> 1 ;
        if ( v[med] <= val )
            st = med + 1;
        else
            dr = med - 1;
    }
    st = ( st + dr ) >> 1 ;
    if ( v[st] > val )
        st--;
    if ( v[st] == val )
        return st ;
    return -1 ;
}
int c1 ( int dr, int val ) {
    int med, st ;
    st = 1 ;
    while ( st < dr ) {
        med = ( st + dr ) >> 1 ;
        if ( v[med] <= val )
            st = med + 1 ;
        else
            dr = med ;
    }
    st = ( st + dr ) >> 1 ;
    if ( v[st] > val )
       st--;
    return st ;
}
int c2 ( int dr, int val ) {
    int med, st ;
    st = 1 ;
    while ( st < dr ) {
        med = ( st + dr ) >> 1 ;
        if ( v[med] < val )
             st = med + 1 ;
        else
            dr = med ;
    }
    st = (st + dr) >> 1 ;
   if ( v[st] < val )
       st++;
    return st ;
}
int main () {
    freopen ( "cautbin.in","r",stdin ) ;
    freopen ( "cautbin.out","w",stdout ) ;
    int i, n, m, op, val ;
    scanf( "%d",&n ) ;
    for (i = 1; i <= n; ++ i)
        scanf( "%d", &v[i] ) ;
    scanf( "%d", &m ) ;
    for ( i = 1 ; i <= m ; i ++ ) {
          scanf ( "%d%d", &op, &val ) ;
          if ( op == 0 )
             printf( "%d\n", c0 ( n, val ) ) ;
          if ( op == 1 )
                printf( "%d\n", c1( n, val ) ) ;
          if (op == 2)
            printf( "%d\n", c2( n, val ) ) ;
    }
    return 0;
}