#include <bits/stdc++.h>
using namespace std ;
ifstream in ("cautbin.in") ;
ofstream out ("cautbin.out") ;
int n , q , v [ 100001 ] ;
int divide0 ( int from , int to , int val )
{
    if ( from == to )
    {
        if ( v [ to ] == val )  return to ;
        if ( v [ to - 1 ] != val )  return -1 ;
        return to - 1 ;
    }
    int mid = ( from + to ) >> 1 ;
    if ( v [ mid ] <= val ) return divide0 ( mid + 1 , to , val ) ;
    else                   return divide0 ( from , mid , val ) ;
}
int divide1 ( int from , int to , int val )
{
    if ( from == to )
    {
        if ( v [ to ] == val )  return to ;
        return to - 1 ;
    }
    int mid = ( from + to ) >> 1 ;
    if ( v [ mid ] <= val ) return divide1 ( mid + 1 , to , val ) ;
    else                   return divide1 ( from , mid , val ) ;
}
int divide2 ( int from , int to , int val )
{
    if ( from == to )
    {
        if ( v [ to ] == val )  return to ;
        return to + 1 ;
    }
    int mid = ( from + to ) >> 1 ;
    if ( v [ mid ] < val ) return divide2 ( mid + 1 , to , val ) ;
    else                   return divide2 ( from , mid , val ) ;
}
int main ()
{
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i )   cin >> v [ i ] ;
    cin >> q ;
    while ( q -- )
    {
        int type , value ;  cin >> type >> value ;
        if ( type == 0 )    cout << divide0( 1 , n , value ) << "\n" ;
        if ( type == 1 )    cout << divide1( 1 , n , value ) << "\n" ;
        if ( type == 2 )    cout << divide2( 1 , n , value ) << "\n" ;
    }
}