#include <stdio.h>

#define NMAX 100000

int v [ NMAX ] ;

using namespace std;

FILE *fin, *fout ;


int caut_bin (int n, int x, int p ) {
  int st, dr, pivot, val;
  st = 0 ;
  dr = n+1 ;
  val = -1 ;

  while ( dr - st > 1 ) {
    pivot = ( st + dr ) / 2 ;
    if (v[pivot] > x )
      dr = pivot ;
    else {
      if (v[pivot] == x ) {
        val = pivot ;
        if (p == 1 || p == 0 )
          st = pivot ;
        else
          dr = pivot ;
      }
      else
        st = pivot ;
    }
  }
  if (p == 0 && val == -1 )  {
    fprintf (fout, "-1" ) ;
    return 0 ;
  }
  else {
    if (p == 0 ) {
      fprintf (fout, "%d\n", val ) ;
    }
    else if (p == 1) {
        fprintf (fout, "%d\n", st ) ;
      }
      else {
        fprintf (fout, "%d\n", dr ) ;
      }
  }
  return 1 ;
}

int main() {
  fin = fopen ("cautbin.in", "r" ) ;
  fout = fopen ("cautbin.out", "w" ) ;

  int n, m, i, x, p ;

  fscanf (fin, "%d", &n ) ;

  for (i = 1 ; i <= n ; i++ ) {
    fscanf (fin, "%d", &v[i] ) ;
  }

  fscanf (fin, "%d", &m ) ;
  for (i = 1 ; i<= m ; i++ ) {
    fscanf (fin, "%d%d", &p, &x ) ;
    caut_bin (n, x, p ) ;
  }

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