#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)
        dr = mij - 1;
      else
        if (a[mij] == x) {
          r = mij;
          st = mij + 1;
        }
        else
          st = mij + 1;
  }
  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) {
      r = mij;
      st = mij + 1;
    }
    else
      dr = mij - 1;
  }
  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 {
      r = mij;
      dr = mij - 1;
    }
  }
  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) << '\n';
    else
      if (c == 1)
        fout << rez1 (v) << '\n';
      else
        fout << rez2 (v) << '\n';

  }
  return 0;
}