#include <fstream>

using namespace std;

int v[100001];

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

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

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

int main() {
  ifstream cin ("cautbin.in");
  ofstream cout ("cautbin.out");
  int n, i, m, x, q;
  cin >> n;
  for (i = 0; i < n; i++)
    cin >> v[i];
  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> q >> x;
    if (q == 0)
      cout << z(x, n) + 1;
    else if (q == 1)
      cout << u(x, n) + 1;
    else
      cout << d(x, n) + 1;
    cout << "\n";
  }
  return 0;
}