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