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

using namespace std;

int bin0(int val, int st, int end, const vector<int> &V, int &r) {
  if(st == end && V[st] == val) {
    return st;
  } else if(st == end && V[st] != val) {
    return r;
  }

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

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

}

int bin2(int val, int st, int end, const vector<int> &V) {
  if(st == end && V[st] == val) {
    return st;
  } else if(st == end && V[st] < val) {
    return st + 1;
  }
  
  int mid = (st + end)/2;
  if(V[mid] >= val) {
    return bin2(val, st, mid - 1, V);
  } else {
    return bin2(val, mid, 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-2, V);
    }
    out << result + 1 << "\n";
  }
  return 0;
}