#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

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

int Bin0(int x, int lim, int n, vector < int > &v) {
  
  int poz = 0, ans = -1;
  for (int bit = lim; bit >= 0; bit --) {
  
    int p = (1 << bit);
    if (v[poz + p] <= x and poz + p <= n) {
      poz += p;
      if (v[poz] == x) {
        ans = poz;
      }
    }
  }

  return ans;
}

int Bin1(int x, int lim, int n, vector < int > &v) {

  int poz = 0, ans = 1;
  for (int bit = lim; bit >= 0; bit --) {

    int p = (1 << bit);
    if (v[poz + p] <= x and poz + p <= n) {
      poz += p;
      ans = poz;
    }
  }

  return ans;
}

int Bin2(int x, int lim, int n, vector < int > &v) {

  int poz = n, ans = n;
  for (int bit = lim; bit >= 0; bit --) {

    int p = (1 << bit);
    if (poz > p and v[poz - p] >= x) {
      poz -= p;
      ans = poz;
    }
  }

  return ans;
}

int main() {

  int n;
  cin >> n;
  int lim = log2(n + 1); 
  vector < int > v(n + 1);
  for (int i = 1; i <= n; i ++) {
    cin >> v[i];
  }

  int m;
  cin >> m;
  while (m --) {

    int type, x;
    cin >> type >> x;
    if (type == 0) {
      cout << Bin0(x, lim, n, v) << '\n';
    }
    else if (type == 1) {
      cout << Bin1(x, lim, n, v) << '\n';
    }
    else {
      cout << Bin2(x, lim, n, v) << '\n';
    }
  }
}