#include <iostream>
#include <fstream>
using namespace std;
 ifstream f("cautbin.in");
 ofstream g("cautbin.out");
int v[100000],n,x,m,i,K,t,k;
int raspuns0(int s,int d,int x)
{
   while(s<=d)
   {
    m=(s+d)/2;
    if(v[m]<=x)
        s=m+1;
    else
        d=m-1;
   }

m=(s+d)/2;
if(v[m]>x)
    m--;
if(v[m]==x)
    g<<m<<"\n";
else
    g<<-1;

    return 0;
}
int raspuns1(int s,int d,int x)
{
    while(s<d)
    {
     m=(s+d)/2;
     if(v[m]<=x)
          s=m+1;
     else
        d=m;
    }
  m=(s+d)/2;
  if(v[m]>x)
    m--;
   g<<m<<"\n";

   return 0;
}
int raspuns2(int s,int d,int x)
{
   while(s<d)
   {
      m=(s+d)/2;
      if(v[m]<x)
        s=m+1;
      else
        d=m;
   }
  m=(s+d)/2;
  if(v[m]<x)
    m++;
  g<<m<<"\n";

  return 0;
}
int main()
{
 f>>n;
 for(i=1;i<=n;i++)
    f>>v[i];

 f>>k;
 for(i=1;i<=k;i++)
 {
    f>>t>>K;
    if(t==0)
        raspuns0(1,n,K);
    if(t==1)
        raspuns1(1,n,K);
    if(t==2)
        raspuns2(1,n,K); }
    return 0;
}