#include<fstream>

using namespace std;

int a[100010],n,m;

int binary0(int p,int u,int v){
    int m;
    
    while(p<u){
         m=p+(u-p)/2;       
         if(a[m]<=v) p=m+1;
            else u=m-1;
            }
       m=p+(u-p)/2;
       if(a[m]>v)--m;
       if(a[m]==v) return m;
    return -1;
}

int binary1(int p,int u,int v){
    int m;
    
    while(p<u){
        m=p+(u-p)/2;
        if(a[m]<=v)p=m+1;
          else u=m;     
               }
      m=p+(u-p)/2;
      if(a[m]>v)m--;
   return m;
}

int binary2(int p,int u,int v){
    int m;
    while(p<u){
        m=p+(u-p)/2;
        if(a[m]<v) p=m+1;
          else u=m;
               }
      m=p+(u-p)/2;
      if(a[m]<v)++m;
    return m;
}

int main(void){
    int sign,value;
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>n;
    for(int i=1;i<=n;++i) fin>>a[i];
    fin>>m; 
    while(m--){
               fin>>sign>>value;   
               if(sign==0) fout<<binary0(1,n,value)<<"\n";
               if(sign==1) fout<<binary1(1,n,value)<<"\n";
               if(sign==2) fout<<binary2(1,n,value)<<"\n";             
               }
 fin.close(); fout.close();
 return 0;                                           
}