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