#include <fstream>

using namespace std;

int const nmax = 100000;

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

int v[1 + nmax];

int cautbin0(int from, int to, int val) {
  if(from == to) {
    if(v[from] == val){
      return from;
    } else {
      return -1;
    }
  } else {
    int mid = (from + to + 1) / 2;
    if(val >= v[mid]) {
      return cautbin0(mid, to, val);
    } else {
      return cautbin0(from, mid - 1, val);
    }
  }
}

int cautbin1(int from, int to, int val) {
  if(from == to) {
    return from;
  } else {
    int mid = (from + 1 + to) / 2;
    if(v[mid] <= val) {
      return cautbin1(mid, to, val);
    } else {
      return cautbin1(from, mid - 1, val);
    }
  }
}

int cautbin2(int from, int to, int val) {
  if(from == to){
    return from;
  } else {
    int mid = (from + to) / 2;
    if(val <= v[mid]){
      return cautbin2(from, mid, val);
    } else {
      return cautbin2(mid + 1, to, val);
    }
  }
}

int main() {
  int n, m, tipq, val;

  in >> n;
  for(int i=1; i<=n; i++) {
    in >> v[i];
  }
  in >> m;
  for(int i=1; i<=m; i++) {
    in >> tipq >> val;
    if(tipq == 0){
      int k = cautbin0(1, n, val);
      out << cautbin0(1, n, val) << "\n";
    } else if(tipq == 1){
      out << cautbin1(1, n, val) << "\n";
    } else {
      out << cautbin2(1, n, val) << "\n";
    }
  }

  return 0;
}