#include <stdio.h>
int n,l,v[100001],i,j,p,x,o;
int cautbin(int s,int d,int x)
{ 
  int m,rez;
  rez=-1;
  while(s<=d)
  {
   m=(s+d)/2;
   if(x<v[m])
    d=m-1;
    else
    if(x==v[m])
    {
               s=m+1;
               rez=m;
    }
else

   if(x>v[m])
   s=m+1;
   if(x==v[m])
    rez=m;
   }
   return rez; 
} 
int cautbin1(int s,int d,int x)
{ 
  int m,rez;
  while(s<=d)
  {
   m=(s+d)/2;
   if(v[m]<=x)
   {
    rez=m;
    s=m+1;
   }
   else
   d=m-1;
  }
   return rez; 
}
int cautbin2(int s,int d,int x)
{ 
  int m,rez;
  while(s<=d)
  {
   m=(s+d)/2;
   if(x<=v[m])
  {
    d=m-1;
    rez=m;
}
else
    s=m+1;
   }
   return rez; 
}     
     
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
     scanf("%d",&v[i]);
    scanf("%d",&l);
    for(i=1;i<=l;i++)
    {
                     scanf("%d %d",&o,&x);
                     if(o==0)
                      printf("%d\n",cautbin(1,n,x));
                     if(o==1) 
                       printf("%d\n",cautbin1(1,n,x));
                     if(o==2) 
                      printf("%d\n",cautbin2(1,n,x));
                     
    }
    return 0;
}