#include <iostream>
#include <fstream>

using namespace std;

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

const int L = 16;
int n,v[100001],M;

int caut0(int x)
{
  int r = 0,pas = 1<<L;
  while (pas != 0)
  {
     if (r + pas <= M && v[r+pas] <= x)
       r += pas;
    pas /= 2;
  }
  if (v[r] != x)
      r = -1;
      return r;
}

int caut1(int x)
{
  int r = 0,pas = 1<<L;
  while (pas != 0)
  {
     if (r + pas <= M && v[r+pas] <= x)
       r += pas;
    pas /= 2;
  }
   return r;
}

int caut2(int x)
{
  int r = 0,pas = 1<<L;
  while (pas != 0)
  {
     if (r + pas <= M && v[r+pas] < x)
       r += pas;
    pas /= 2;
  }
  r++;
   return r;
}

int main()
{
    int i,j,x;
    in >> n;
    for (i=1; i<=n; i++)
         in >> v[i];
    in >> M;
    for (i=1; i<=M; i++)
    {
        in >> j >> x;
        if (j == 0)
          out << caut0(x)+1 << "\n";
        if (j == 1)
           out << caut1(x)+1 << "\n";
        if (j == 2)
           out << caut2(x) << "\n";
    }
    return 0;
}