#include <bits/stdc++.h>
#define ll long long
#define ui unsigned int
using namespace std;
 
int n,m,i,j;
unsigned int st,dr,mid,fin=1,a[100010],x,y;
int cb0(ui st,ui dr)
{ 
 mid=(st+dr)/2;
 if(st>dr) if(a[dr]==y) return dr; else return -1;
 if(a[mid]>y) {
 cb0(st,mid-1);}
 else cb0(mid+1,dr);
}
int cb1(ui st,ui dr)
{ 
 mid=(st+dr)/2;
 if(st>dr) return dr; 
 if(a[mid]>y) {
 cb1(st,mid-1);}
 else cb1(mid+1,dr);
}
int cb2(ui st,ui dr)
{ 
 mid=(st+dr)/2;
 if(st>dr) return st; 
 if(a[mid]>=y) {
 cb2(st,mid-1);}
 else cb2(mid+1,dr);
}

                                                                     //  1 2 3 4 4 4 5 6 7 8 8 12
 
int main()
{
   ifstream cin("cautbin.in");
   ofstream cout("cautbin.out");
    
   cin>>n;
   for(i=1;i<=n;i++) cin>>a[i];
   cin>>m;
   for(j=1;j<=m;j++)
   {
      cin>>x>>y;
        if(x==0){
        
             cout<<cb0(1,n)<<"\n";
            
           }
        if(x==1)
        {
             cout<<cb1(1,n)<<"\n";
        }
        if(x==2)
        {
                cout<<cb2(1,n)<<"\n";    
            }
        }
    
     return 0; 
}