#include <bits/stdc++.h>
#define L 100005
#define RI_MAX (1 << 17)
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[L], n;

inline int cb1(int x){
  int r = 0, step = RI_MAX;
  while (step){
    if (r + step <= n && v[r + step] <= x)
      r += step;
    step /= 2;
  }
  return r;
}

inline int cb0(int x){
  int r = cb1(x);
  if (v[r] != x)
    r = -1;
  return r;
}

inline int cb2(int x){
  int r;
  if (cb0(x) == -1)
    r = cb1(x) + 1;
  else
    r = cb1(x - 1) + 1;
  return r;
}

int main(){
  int i, m, t, x;
  fin >> n;
  for (i = 1; i <= n; i++)
    fin >> v[i];
  for (fin >> m; m; m--){
    fin >> t >> x;
    if (t == 0)
      fout << cb0(x) << "\n";
    else if (t == 1)
      fout << cb1(x) << "\n";
    else
      fout << cb2(x) << "\n";
  }
  return 0;
}