#include <fstream>
#include <vector>

using namespace std;

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

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

  int st = 1, dr = n, ans = -1;
  while (st <= dr) {

    int mid = st + (dr - st) / 2; 
    if (v[mid] <= x) {
      if (v[mid] == x) {
        ans = mid;
      }  
      st = mid + 1;
    }
    else {
      dr = mid - 1;
    }
  }

  return ans;
}

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

  int st = 1, dr = n, ans = -1;
  while (st <= dr) {

    int mid = st + (dr - st) / 2;
    if (v[mid] <= x) {
      ans = mid;
      st = mid + 1;
    }
    else {
      dr = mid - 1;
    }
  }

  return ans;
}

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

  int st = 1, dr = n, ans = 2e9;
  while (st <= dr) {

    int mid = st + (dr - st) / 2;;
    if (v[mid] >= x) {
      ans = mid;
      dr = mid - 1;
    }
    else {
      st = mid  + 1;
    }
  }

  return ans;
}

int main() {

  int n;
  cin >> n;
  
  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, n, v) << '\n';
    }
    else if (type == 1) {
      cout << Bin1(x, n, v) << '\n';
    }
    else {
      cout << Bin2(x, n, v) << '\n';
    }
  }
}