#include<stdio.h> 
 long v[100010],n,m;  
   
 void read()  
 {  
 scanf("%ld",&n);  
 long i;  
 for (i=1;i<=n;i++)  
      scanf("%ld",&v[i]);  
 scanf("%ld",&m);  
 }  
   
 long cautbin(long st,long dr,long k)  
 {  
 long w,m;  
 w=-1;  
 while (st<=dr)  
       {  
        m=(st+dr)/2;  
        if (v[m]==k)  
           {  
            w=m;  
            st=m+1;  
           }  
       else if (v[m]<k)  
               {  
                st=m+1;  
               }  
             else {  
                   dr=m-1;  
                  }  
       }  
 return w;  
 }  
   
 long cautbin1(long st,long dr,long k)  
 {  
 long w,m;  
 w=-1;  
 while (st<=dr)  
       {  
        m=(st+dr)/2;  
        if (v[m]<=k)  
           {  
            w=m;  
            st=m+1;  
           }  
       else {  
             dr=m-1;  
            }  
       }  
 return w;  
 }  
   
 long cautbin2(long st,long dr,long k)  
 {  
 long w,m;  
 w=-1;  
 while (st<=dr)  
       {  
        m=(st+dr)/2;  
        if (v[m]>=k)  
           {  
            w=m;  
            dr=m-1;  
           }  
       else {  
             st=m+1;  
            }  
       }  
 return w;  
 }  
   
 void rez()  
 {  
 long a,b;  
 long i;  
 for (i=1;i<=m;i++)  
     {  
      scanf("%ld%ld",&a,&b);  
      if (a==0)  
         printf("%ld\n",cautbin(1,n,b));  
       else if (a==1)  
                printf("%ld\n",cautbin1(1,n,b));  
            else printf("%ld\n",cautbin2(1,n,b));  
     }  
 }  
   
 int main()  
 {  
 freopen("cautbin.in","r",stdin);  
 freopen("cautbin.out","w",stdout);  
 read();  
 rez();  
 return 0;  
 }