#include <fstream>

using namespace std;

int n, q, tip, x, a[100005], p, u , m;

int bs0 (int x) {
  p = 1, u = n;
  while (p <= u) {
    m = (p+u)/2;
    if (a[m] <= x)
      p = m+1;
    else
      u = m-1;
  }
  m = (p+u)/2;
  if (a[m] > x)
    m--;
  if (a[m] == x)
    return m;
  return -1;
}

int bs1 (int x) {
  p = 1, u = n;
  while (p < u) {
    m = (p+u)/2;
    if (a[m] <= x)
      p = m+1;
    else
      u = m;
  }
  m = (p+u)/2;
  if (a[m] > x)
    m--;
  return m;
}

int bs2 (int x) {
  p = 1, u = n;
  while (p < u) {
    m = (p+u)/2;
    if (a[m] < x)
      p = m+1;
    else
      u = m;
  }
  m = (p+u)/2;
  if (a[m] < x)
    m++;
  return m;
}

int main () {
  ifstream fin("cautbin.in");
  ofstream fout("cautbin.out");
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> a[i];
  fin >> q;
  for (int i = 1; i <= q; i++) {
    fin >> tip >> x;
    if (tip == 0)
      fout << bs0(x) << '\n';
    else
      if (tip == 1)
        fout << bs1(x) << '\n';
      else
        fout << bs2(x) << '\n';
  }
  return 0;
}