#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("cautbin.in") ;
ofstream fout ("cautbin.out") ;

int n , A [100001] , m ;
void Citire()
{
    int i ;
    fin >> n;
    for ( i = 1 ; i <= n ; ++ i )
          fin >> A[i];
    fin >> m ;
}

int CautareBinara ( int n , int A[] , int val )
{
    int i , step , poz = -1 ;

    for ( step = 1 ; step < n ;step = step << 1 ) ;

    for ( i = 0 ; step ; step >>= 1 )
       if ( i + step < n && A [i+step] <= val )
             i += step , poz = i ;

    return poz ;
}

int CautareBinara2 ( int n , int A[] , int val )
{
    int i , step , poz = -1 ;
    for ( step = 1 ; step < n ;step <<= 1 );

    for ( i = 0 ; step ; step >>= 1 )
       if ( i + step < n && A [i+step] <= val )
             i += step , poz = i ;

    if ( poz == -1 )
          return ( poz = -- i ) ;
    else
    {
       while ( poz != n && A [poz] == A[poz + 1 ] )
                     ++ poz ;
        return poz ;

    }
}

int CautareBinara3 ( int n , int A[] , int val )
{
    int i , step , poz = -1 ;
    for ( step = 1 ; step < n ;step <<= 1 );

    for ( i = 0 ; step ; step >>= 1 )
       if ( i + step < n && A [i+step] <= val )
             i += step , poz = i ;

    if ( poz == -1 )
         return ( poz = ++ i )  ;
    else
    {
        while ( poz != 1 && A [poz] == A[poz - 1 ] )
                     -- poz ;
        return poz ;
    }

}

void Rezolvare ()
{
    int x1 , x2 ;
    while ( m >= 1 )
    {
        fin >> x1 >> x2 ;
        switch (x1)
        {
            case 0 : fout << CautareBinara ( n , A , x2 ) << "\n" ; break ;
            case 1 : fout << CautareBinara2 ( n , A , x2 ) << "\n" ; break ;
            case 2 : fout << CautareBinara3 ( n , A , x2 ) << "\n" ; break ;
        }
     -- m ;
    }
}
int main()
{
    Citire();
    Rezolvare() ;
    return 0;
}