#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int bin0(int val, int st, int end, const vector<int> &V, int &r) {
  if (end - st <= 1) {
    for (int i = end; i >= st; i--) {
      if (V[i] == val) {
        return i;
      }
    }
    return -2;
  }


  int mid = (st + end)/2;
  if(val >= V[mid]) {
    return bin0(val, mid, end, V, r);
  }
  return bin0(val, st, mid - 1, V, r);
}

int bin1(int val, int st, int end, const vector<int> &V) {
  if (end - st <= 1) {
    for (int i = end; i >= st; i--) {
      if (V[i] <= val) {
        return i;
      }
    }
  }

  int mid = (st + end) / 2;
  if(V[mid] <= val) {
    return bin1(val, mid, end, V);
  } else {
    return bin1(val, st, mid - 1, V);
  }

}

int bin2(int val, int st, int end, const vector<int> &V) {
  if (end - st <= 1) {
    for (int i = st; i <= end; i++) {
      if (V[i] >= val) {
        return i;
      }
    }
  }

  int mid = (st + end)/2;
  if(V[mid] >= val) {
    return bin2(val, st, mid, V);
  } else {
    return bin2(val, mid + 1, end, V);
  }
}

int main() {
  ifstream in("cautbin.in");
  ofstream out("cautbin.out");
  int N, Q, n, q, v;
  vector<int> V;
  in >> N;
  for(int i = 0; i < N; i++) {
    in >> n;
    V.push_back(n);
  }
  in >> Q;
  for(int i = 0; i < Q; i++) {
    int r = -1, result;
    in >> q >> v;
    if(q == 0) {
      result = bin0(v, 0, N-1, V, r);
    } else if(q == 1) {
      result = bin1(v, 0, N-1, V);
    } else {
      result = bin2(v, 0, N-1, V);
    }
    out << result + 1 << "\n";
  }
  return 0;
}