#include <iostream>
#include <fstream>

using namespace std;
const int N=1000001;

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

int v[N],n,i,k;

int caut_bin0( int v[N],int k,int n)
{int m,st=0,dr=n ;
     while(st<=dr)
     {
          m=(st+dr)/2;
          if (v[m]<=k) st=m+1;
          else dr=m-1;
     }
  m=(st+dr)/2;
  if (v[m]>k)
  m=m-1;
  if (v[m]==k)
  return m;
  else return -1;
 }int caut_bin1(int v[N],int k,int n)
{
     int m,st=0,dr=n;
     while(st<dr)
     {
          m=(st+dr)/2;
          if (v[m]<=k) st=m+1;
          else dr=m;
     }
m=(st+dr)/2;
if (v[m]>k) m--;
return m;
}

int caut_bin2(int v[N],int k,int n)
{
    int m,st=0,dr=n;
     while(st<dr)
     { m=(st+dr)/2;
       if (v[m]<k) st=m+1;
       else dr=m;
     }
m=(st+dr)/2;
if (v[m]<k) m++;
return m;
}

int main()
{
    int p,t,x,y;
    in>>n;
    for (i=1;i<=n;i++)
        in>>v[i];
    in>>t;
    for (i=1;i<=t;i++)
        {in>>x>>y;
        if (x==0) out<<caut_bin0 (v,y,n)<<"\n";
        if (x==1) out<<caut_bin1  (v,y,n)<<"\n";
        if (x==2) out<<caut_bin2 (v,y,n)<<"\n";}
    return 0;
}