#include <iostream>
#include <fstream>
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n, m, q, x, v[100005];

int solveFirstCase(int lo, int hi, int x) {
  int mid;

  while (lo <= hi) {
    mid = (lo + hi) / 2;
    if (v[mid] <= x) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  mid = (lo + hi) / 2;

  if (v[mid] > x) {
    mid--;
  }
  if (v[mid] == x) {
    return mid;
  }
  return -1;
}

int solveSecondCase(int lo, int hi, int x) {
  int mid;

  while (lo < hi) {
    mid = (lo + hi) / 2;
    if (v[mid] <= x) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  mid = (lo + hi) / 2;

  if (v[mid] > x) {
    mid--;
  }
  return mid;
}

int solveThirdCase(int lo, int hi, int x) {
  int mid;

  while (lo < hi) {
    mid = (lo + hi) / 2;
    if (v[mid] < x) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  mid = (lo + hi) / 2;

  if (v[mid] < x) {
    mid++;
  }
  return mid;
}

int main() {
  f >> n;
  for (int i = 1; i <= n; i++) {
    f >> v[i];
  }
  f >> m;
  while (m--) {
    f >> q >> x;
    if (q == 0) {
      g << solveFirstCase(1, n, x);
    } else if (q == 1) {
      g << solveSecondCase(1, n, x);
    } else {
      g << solveThirdCase(1, n, x);
    }
    g << "\n";
  }
}