/**  Care sunt sansele sa ia 100? **/
#include <stdio.h>

#define Nadejde 100000

int N, M;
int sorted[Nadejde];

int low(int X, int Y) {
  return X < Y;
}

int loworEqual(int X, int Y) {
  return X <= Y;
}

/** Cautare binara generalizata. **/
int bSearch(int lo, int hi, int x, int cmp(int, int), int add) {
  while (hi - lo > 1) {
    int mid = (lo + hi) >> 1;
    if (cmp(sorted[mid], x)) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  return lo + add;
}

int main(void) {
  int i, task, x, result;
  FILE *f = fopen("cautbin.in", "r");

  /* Citirea datelor. */
  fscanf(f, "%d", &N);
  for (i = 0; i < N; i++) {
    fscanf(f, "%d", &sorted[i]);
  }
  /* Raspunde la intrebari. */
  freopen("cautbin.out", "w", stdout);
  for (fscanf(f, "%d", &M); M; M--) {
    fscanf(f, "%d %d", &task, &x);
    if (task == 0) {
      result = bSearch(-1, N, x, loworEqual, 0);
      if (sorted[result] != x) {
        result = -1;
      } else {
        result++;
      }
    } else if (task == 1) {
      result = bSearch(-1, N, x, loworEqual, 0) + 1;
    } else {
      result = bSearch(-1, N, x, low, 1) + 1;
    }
    fprintf(stdout, "%d\n", result);
  }
  fclose(f);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}