#include <fstream>

using namespace std;

long a[100100],n,m,i,x,y,lg,step;

long keres1(long mit)
{
  long st=lg,q;
  for (q=0;st>0;st>>=1)
   if (q+st<=n&&a[q+st]<=mit) q+=st;

  if (a[q]==mit) return q;
  return -1;
}

long keres2(long mit)
{
  long st=lg,q;
  for (q=0;st>0;st>>=1)
   if (q+st<=n&&a[q+st]<=mit) q+=st;

  return q;
}

long keres3(long mit)
{
  long st=lg,q;
  for (q=n;st>0;st>>=1)
   if (q-st>0&&a[q-st]>=mit) q-=st;

  return q;
}


int main()
{
  ifstream in("cautbin.in");
  ofstream out("cautbin.out");

  in >> n;

  for (lg=1; lg<n; lg <<= 1);

  for (i=1;i<=n;++i) in >> a[i];
  in >> m;
  for (i=1;i<=m;++i)
  {
    in >> x >> y;
    if (x==0) out << keres1(y) << "\n"; else
    if (x==1) out << keres2(y) << "\n"; else
    out << keres3(y) << "\n";
  }

  in.close();
  out.close();

  return 0;
}