#include <iostream>
#include <fstream>

using namespace std;

int n, m, type, val, result;
int v[100002];

int calc_bin_v1() {
  int left = 0, right = n - 1, middle, result = -2;
  while (left <= right) {
    middle = (left + right) / 2;
    if (v[middle] <= val) {
      left = middle + 1;
      if (v[middle] == val) {
        result = middle;
      }
    }
    else {
      right = middle - 1;
    }
  }
  return result;
}

int calc_bin_v2() {
  int left = 0, right = n - 1, middle;
  while (left <= right) {
    middle = (left + right) / 2;
    if (v[middle] <= val) {
      left = middle + 1;
    }
    else {
      right = middle - 1;
    }
  }
  return left - 1;
}

int calc_bin_v3() {
  int left = 0, right = n - 1, middle;
  while (left <= right) {
    middle = (left + right) / 2;
    if (v[middle] >= val) {
      right = middle - 1;
    }
    else {
      left = middle + 1;
    }
  }
  return right + 1;
}

int calc_bin() {
  if (type == 0) {
    return calc_bin_v1();
  }
  if (type == 1) {
    return calc_bin_v2();
  }
  return calc_bin_v3();
}

int main() {
  ifstream fin("cautbin.in");
  ofstream fout("cautbin.out");

  fin >> n;
  for(int i = 0; i < n; i++) {
    fin >> v[i];
  }

  fin >> m;
  for(int i = 0; i < m; i++) {
    fin >> type >> val;
    fout << calc_bin() + 1 << std::endl;
  }

  fin.close();
  fout.close();
  return 0;
}