#include <cstdio>
#include <cstdlib>
#include <time.h>

const int MAX_N = 100000;

int v[MAX_N];

int random(int a, int b) {
  return rand() % (b - a + 1) + a;
}

int cautare(int st, int dr, int val) {
  int mid;
  while(dr - st > 1) {
    mid = random(st, dr - 1);
    if(val < v[mid])
      dr = mid;
    else
      st = mid;
  }
  return st;
}

int cautare2(int st, int dr, int val) {
  int mid;
  while(dr - st > 1) {
    mid = random(st, dr - 1);
    if(val <= v[mid])
      dr = mid;
    else
      st = mid;
  }
  return dr;
}

int main() {
  srand(time(NULL));
  int n, i, q, x, tipQuery, poz;
  FILE *fin = fopen( "cautbin.in" , "r" );
  fscanf(fin, "%d", &n);
  for(i = 0; i < n; i++)
    fscanf(fin, "%d", &v[i]);

  FILE *fout = fopen( "cautbin.out" , "w" );

  fscanf(fin, "%d", &q);
  for(i = 0; i < q; i++) {
    fscanf(fin, "%d%d", &tipQuery, &x);
    if(tipQuery == 0) {
      poz = cautare(0, n, x);
      if(v[poz] == x)
        fprintf(fout, "%d\n", poz + 1);
      else
        fprintf(fout, "-1\n");
    } else if(tipQuery == 1) {
      poz = cautare(0, n, x);
      fprintf(fout, "%d\n", poz + 1);
    } else {
      poz = cautare2(-1, n - 1, x);
      fprintf(fout, "%d\n", poz + 1);
    }
  }

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