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

using namespace std;

ifstream fin ("cautbin.in");
ofstream fout ("cautbin.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 (place >=1 && place <= N && a[place] == x) fout << place << "\n";
        else fout << "-1\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;
}