#include <cstdio>
#include <cstdlib>

using namespace std ;

int vector [ 100001 ] ;
int nrElemente , nrInstructiuni ;

void citireStart ( ) ;

void citireVector ( ) ;

void executareInstructiune ( int & ) ;

void optiunea1 ( int & ) ;

void optiunea2 ( int & ) ;

void optiunea0 ( int & ) ;

int main ( )
{
  freopen ( "cautbin.in" , "r" , stdin ) ;
  freopen ( "cautbin.out" , "w" , stdout ) ;
  int optiune ;
  scanf ( "%d" , &nrElemente ) ;
  citireVector ( ) ;
  scanf ( "%d" , &nrInstructiuni ) ;
  for ( int i = 0 ; i < nrInstructiuni ; ++i )
    executareInstructiune ( optiune ) ;
  return 0 ;
}

void citireVector ( )
{
  for ( int i = 0 ; i < nrElemente ; ++i )
    scanf ( "%d" , &vector [ i ] ) ;
  return ;
}

void executareInstructiune ( int &Opt )
{
  scanf ( "%d" , &Opt ) ;
  switch ( Opt )
  {
    case 0 : { optiunea0 ( Opt ) ; break ; } 
    case 1 : { optiunea1 ( Opt ) ; break ; }
    case 2 : { optiunea2 ( Opt ) ; break ; }
  }
}

void optiunea0 ( int &Opt )
{
  int mid ;
  scanf ( "%d" , &Opt ) ;
  int cap = 0 , coada = nrElemente - 1 ;
  if ( vector [ coada ] == Opt )
  {
    printf ( "%d\n" , coada + 1 ) ;
  }
  while ( coada - cap > 1 )
  {
    mid = ( cap + coada ) >> 1 ;
    if ( vector [ mid ] > Opt )
      coada = mid ;
    else
      cap = mid ;
  }
  if ( vector [ coada ] == Opt )
    printf ( "%d\n" , coada + 1 ) ;
  else if ( vector [ cap ] == Opt )
    printf ( "%d\n" , cap + 1 ) ;
  else
    printf ( "-1\n" ) ;
  return ;
}

void optiunea1 ( int &Opt )
{
  int mid ;
  scanf ( "%d" , &Opt ) ;
  int cap = 0 , coada = nrElemente - 1 ;
  if ( vector [ coada ] <= Opt )
  {
    printf ( "%d\n" , coada + 1) ;
    return ;
  }
  while ( coada - cap > 1 )
  {
    mid = ( cap + coada ) >> 1 ;
    if ( vector [ mid ] > Opt )
      coada = mid ;
    else
      cap = mid ;
  }
  printf ( "%d\n" , cap + 1) ;
  return ;
}

void optiunea2 ( int &Opt ) 
{
  int mid ;
  scanf ( "%d" , &Opt ) ;
  int cap = 0 , coada = nrElemente - 1 ;
  if ( vector [ cap ] >= Opt )
  {
    printf ( "%d\n" , coada + 1 ) ;
    return ;
  }
  while ( coada - cap > 1 )
  {
    mid = ( cap + coada ) >> 1 ;
    if ( vector [ mid ] < Opt )
      cap = mid ;
    else
      coada = mid ;
  }
  printf ( "%d\n" , coada + 1 ) ;
  return ;
}