#include <fstream>
#define NMAX 100000
#define MAXLOG 16

using namespace std;

ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");

int n;
int v[NMAX + 1];

int bs(int op, int val) {
  int i, pozcur;

  pozcur = 0;
  for (i = MAXLOG; i >= 0; i--) {
    if ((op == 0 || op == 1) && pozcur + (1 << i) <= n && v[pozcur + (1 << i)] <= val)
      pozcur += (1 << i);
    else if (op == 2 && pozcur + (1 << i) <= n && v[pozcur + (1 << i)] < val)
      pozcur += (1 << i);
  }

  if (op == 0 && v[pozcur] != val)
    return -1;
  return pozcur;
}

int main() {
  int i, q, op, val;
  cin >> n;

  for (i = 1; i <= n; i++)
    cin >> v[i];

  cin >> q;
  while (q--) {
    cin >> op >> val;
    if (op == 0 || op == 1)
      cout << bs(op, val) << "\n";
    else
      cout << bs(op, val) + 1 << "\n";
  }
  return 0;
}