#include <stdio.h>

int v[100001], n;
int cautare0( int x ){
  int st, dr, mid;
  st = 1;
  dr = n;
  while ( st <= dr ) {
    mid = ( st + dr ) / 2;
    if ( v[mid] <= x )
      st = mid + 1;
    else
      dr = mid - 1;
  }
  mid = ( st + dr ) / 2;
  if ( v[mid] > x )
    mid--;
  if ( v[mid] != x )
    return -1;
  return mid;
}
int cautare1( int x ){
  int st, dr, mid;
  st = 1;
  dr = n;
  while ( st < dr ){
    mid = ( st + dr ) / 2;
    if ( v[mid] <= x )
      st = mid + 1;
    else
      dr = mid;
  }
  mid = ( st + dr ) / 2;
  if ( v[mid] > x )
    mid--;
  return mid;
}
int cautare2( int x ){
  int st, dr, mid;
  st = 1;
  dr = n;
  while ( st < dr ) {
    mid = ( st + dr ) / 2;
    if ( v[mid] < x )
      st = mid + 1;
    else
      dr = mid;
  }
  mid = ( st + dr ) / 2;
  if ( v[mid] < x )
    mid++;
  return mid;
}
int main(){
  FILE *fin, *fout;
  fin = fopen( "cautbin.in", "r" );
  fout = fopen( "cautbin.out", "w" );

  int m, i, op, x;
  fscanf( fin, "%d", &n );
  for ( i = 1; i <= n; i++ )
    fscanf( fin, "%d", &v[i] );
  fscanf( fin, "%d", &m );
  for ( i = 0; i < m; i++ ){
    fscanf( fin, "%d%d", &op, &x );
    if ( op == 0 )
      fprintf( fout, "%d\n", cautare0( x ) );
    else if ( op == 1 )
      fprintf( fout, "%d\n", cautare1( x ) );
    else
      fprintf( fout, "%d\n", cautare2( x ) );
  }

  fclose( fin );
  fclose( fout );
  return 0;
}