#include <bits/stdc++.h>
using namespace std ;
const int NR = 100005 ;
ifstream in ( "cautbin.in" ) ;
ofstream out ( "cautbin.out" ) ;
int v [ NR ] , n , key , type , q , i ;
int dei0 ( int from , int to , int key )
{
    if ( to - from <= 1 )
    {
        if ( v [ to ] == key )  return to ;
        if ( v [ from ] == key )    return from ;
        return -1 ;
    }
    int mid = ( from + to ) >> 1 ;
    if ( key > v [ mid ] )  return dei0 ( mid , to , key ) ;
    if ( key < v [ mid ] )  return dei0 ( from , mid , key ) ;
    if ( key == v [ mid ] ) return dei0 ( mid , to , key ) ;
}

int dei1 ( int from , int to , int key )
{

    if ( to - from <= 1 )
    {
        if ( v [ to ] <= key )  return to ;
        return from ;

    }


    int mid = ( from + to ) >> 1 ;
    if ( key > v [ mid ] )  return dei1 ( mid , to , key ) ;
    if ( key < v [ mid ] )  return dei1 ( from , mid , key ) ;
    if ( key == v [ mid ] ) return dei1 ( mid , to , key ) ;
}

int dei2 ( int from , int to , int key )
{

    if ( to - from <= 1 )
    {
        if ( v [ from ] >= key )    return from ;
        return to ;

    }

    int mid = ( from + to ) >> 1 ;
    if ( key > v [ mid ] )  return dei2 ( mid , to , key ) ;
    if ( key < v [ mid ] )  return dei2 ( from , mid , key ) ;
    if ( key == v [ mid ] ) return dei2 ( from , mid , key ) ;
}

int main ()
{
    in >> n ;
    for ( i = 1 ; i <= n ; ++ i )   in >> v [ i ] ;
    in >> q ;
    while ( q -- )
    {
        in >> type >> key ;
        if ( !type )        out << dei0( 1 , n , key ) << '\n' ;
        if ( type == 1 )    out << dei1( 1 , n , key ) << '\n' ;
        if ( type == 2 )    out << dei2( 1 , n , key ) << '\n' ;
    }
 }