#include<fstream>
using namespace std;
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");
long long int a[1000000],m,n;
int cautare0(int i,int j,int x){
    int m;
   while(i<=j){
               m=(i+j)/2;
               if(a[m]<=x)
               i=m+1;
               else 
               j=m-1;
               }
             m=(i+j)/2;
             if(a[m]>x) m--;
             if(a[m]==x) return m;
             else return -1;  
    
    
    
    }
    int cautare1(int i,int j,int x){
        int m;
        while(i<j){
                    m=(i+j)/2;
                    if(a[m]<=x)
                    i=m+1;
                    else 
                    j=m;
                    
                    
                    }
        m=(i+j)/2;
        if(a[m]>x) --m;
        return m;
        
        
        }
        int cautare2(int i,int j,int x){
            int m;
            while(i<j){
                        m=(i+j)/2;
                        if(a[m]<x)
                        i=m+1;
                        else 
                        j=m;
                        }
                        m=(i+j)/2;
                        if(a[m]<x) m++;
                        return m;
                        
                        
                        
                        }
            int main(){
                long long int t,x;
              fi>>n;
              for(int i=1;i<=n;i++)
                 fi>>a[i];
                 fi>>m;
                for(int i=1;i<=m;i++){
                        
                        fi>>t>>x;
                        if(t==0) fo<<cautare0(1,n,x)<<endl;
                        if(t==1) fo<<cautare1(1,n,x)<<endl;
                        if(t==2) fo<<cautare2(1,n,x)<<endl;
                        
                        
                        }
                return 0;
                
                
                }