#include <bits/stdc++.h>

using namespace std;

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

int main(){
  int n; fin >> n;
  vector<int>v(n);
  for (int &x : v){
    fin >> x;
  }
  int q; fin >> q;
  while (q--){
    int o, x; fin >> o >> x;
    if (o == 0){
      if (!binary_search(v.begin(), v.end(), x)){
        fout << -1 << '\n';
      }
      else{
        fout << upper_bound(v.begin(), v.end(), x) - v.begin() << '\n';
      }
    }
    else if (o == 2){
      fout << lower_bound(v.begin(), v.end(), x) - v.begin() + 1 << '\n';
    }
    else if (o == 1){
      fout << upper_bound(v.begin(), v.end(), x) - v.begin() << '\n';
    }
  }
}