#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

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

int N, x, cod, place, K, a[100009];

int main ()
{
  fin >> N;
  for (int i=1; i<=N; i++)
    fin >> a[i];

   fin >> K;
  for (int i=1; i<=K; i++)
  {
      fin >> cod >> x;

      if (cod == 0)  /// cea mai din dreapta pozitie unde poate fi inserat x fara sa strice rel de ordine
      {
        place = upper_bound(a+1, a+N+1, x) - a - 1;
        if (a[place] != x) fout << "\-1";
        else  fout << place << "\n";
      }

       else if (cod == 1) /// cea mai din dreapta poz unde poate fi x sau un nr mai mic decat x
      {
        place = lower_bound(a+1, a+N+1, x + 1) - a - 1;
        fout << place << "\n";
      }

      else /// cod == 2
      {
        place = upper_bound(a+1, a+N+1, x - 1) - a;
        fout << place << "\n";
      }
  }
  fin.close();
  fout.close();
  return 0;
}