#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
int n, i, m, a, b, mij;
int v[100001];
int cautare0(int in, int sf, int val) {
  while (in <= sf) {
    mij = (in + sf) / 2;
    if (v[mij] <= val)
      in = mij + 1;
    else
      sf = mij - 1;
  }
  mij = (in + sf) / 2;
  if (v[mij] > val)
    mij--;
  if (v[mij] == val)
    return mij;
  return -1;
}
int cautare1(int in, int sf, int val) {
  while (in < sf) {
    mij = (in + sf) / 2;
    if (v[mij] <= val)
      in = mij + 1;
    else
      sf = mij;
  }
  mij = (in + sf) / 2;
  if (v[mij] > val)
    mij--;
  return mij;
}
int cautare2(int in, int sf, int val) {
  while (in < sf) {
    mij = (in + sf) / 2;
    if (v[mij] < val)
      in = mij + 1;
    else
      sf = mij;
  }
  mij = (in + sf) / 2;
  if (v[mij] < val)
    mij++;
  return mij;
}
int main () {
  fin >> n;
  for (i = 1; i <= n; i++)
    fin >> v[i];
  fin >> m;
  for (i = 1; i <= m; i++) {
    fin >> a >> b;
    switch (a) {
      case 0:
        fout << cautare0(1, n, b) << '\n';
        break;
      case 1:
        fout << cautare1(1, n, b) << '\n';
        break;
      case 2:
        fout << cautare2(1, n, b) << '\n';
        break;
    }
  }
  fin.close();
  fout.close();
  return 0;
}