#include<stdio.h>  
    #define N_M 100005  
    #define FIN "cautbin.in"  
    #define FOUT "cautbin.out"  
    int v[N_M],n,m;  
      
    int zero(int target)  
        {  
       int lo=1,hi=n,mid;  
       while(lo<=hi)  
           {  
           mid=lo+(hi-lo)/2;  
           if(v[mid]==target)return mid;  
           else if(v[mid]<target)lo=mid+1;  
           else hi=mid-1;  
           }  
       return -1;  
       }  
     
   int unu(int target)  
       {  
       int lo=1,hi=n,mid,w=1;  
       while(lo<=hi)  
           {  
           mid=lo+(hi-lo)/2;  
           if(v[mid]<=target){w=mid;lo=mid+1;}  
           else hi=mid-1;  
           }  
       return w;  
       }  
     
 int doi(int target)  
     {int lo=1,hi=n,mid,w=n+1;  
     while(lo<=hi)  
         {  
         mid=lo+(hi-lo)/2;  
         if(target<=v[mid]){w=mid;hi=mid-1;}  
         else lo=mid+1;  
         }  
     return w;  
     }
    
   void read_write()  
      {int x,target;  
      int i;  
      freopen(FIN,"r",stdin);  
     freopen(FOUT,"w",stdout);  
 scanf("%d",&n);  
     for(i=1;i<=n;i++)  
         scanf("%d ",&v[i]);  
  scanf("%d",&m);  
     for(i=1;i<=m;i++)  
          {  
           scanf("%d %d",&x,&target);  
        if(!x)printf("%d\n",zero(target));  
         else if(x==1)printf("%d\n",unu(target));  
         else printf("%d\n",doi(target));  
        }  
     }  
  
  int main()  
      {  
      read_write();  
     return 0;  
       }