#include <fstream>

using namespace std;

ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");

int n, a[100001], m, c, v;

int rez0 (int x) {
  int st = 1, dr = n, mij;
  int r = -1;
  while (st <= dr) {
    mij = st + (dr - st) / 2;
    if (a[mij] <= x)
      st = mij + 1;
    else
      dr = mij - 1;
  }
  mij = st + (dr - st) / 2;
  if (a[mij] > x)
    mij--;
  if (a[mij] == x)
    r = mij;
  return r;
}

int rez1 (int x) {
  int st = 1, dr = n, mij;
  int r = 0;
  while (st < dr) {
    mij = st + (dr - st) / 2;
    if (a[mij] <= x)
      st = mij + 1;
    else
      dr = mij;
  }
  mij = st + (dr - st) / 2;
  if (a[mij] > x)
    mij--;
  r = mij;
  return r;
}

int rez2 (int x) {
  int st = 1, dr = n, mij;
  int r = 0;
  while (st < dr) {
    mij = st + (dr - st) / 2;
    if (a[mij] < x)
      st = mij + 1;
    else
      dr = mij;
  }
  mij = st + (dr - st) / 2;
  if (a[mij] < x)
    mij++;
  r = mij;
  return r;
}

int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> a[i];
  fin >> m;
  for (int i = 1; i <= m; i++) {
    fin >> c >> v;
    if (c == 0)
      fout << rez0 (v) << endl;
    else
      if (c == 1)
        fout << rez1 (v) << endl;
      else
        fout << rez2 (v) << endl;

  }
  return 0;
}