#include<fstream>
#define maxn 100005
using namespace std;
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");

int i,n,q,x,k,v[maxn];

int bsearch0(int x,int st,int dr){
    int mijl;
    
    while(st<dr){
                 mijl=(st+dr)/2;
                 if(v[mijl]<=x) st=mijl+1;
                 else dr=mijl-1;
                }
    
    mijl=(st+dr)/2;
    if(v[mijl]>x) mijl--;
    if(v[mijl]==x) return mijl;
    else return (-1);
}

int bsearch1(int x,int st,int dr){
    int mijl;
    
    while(st<dr){
                 mijl=(st+dr)/2;
                 if(v[mijl]<=x) st=mijl+1;
                 else dr=mijl;
                }
                
    mijl=(st+dr)/2;
    if(v[mijl]>x) mijl--;
    return mijl;
}

int bsearch2(int x,int st,int dr){
    int mijl;
    
    while(st<dr){
                 mijl=(st+dr)/2;
                 if(v[mijl]<x) st=mijl+1;
                 else dr=mijl;
                }
                
    mijl=(st+dr)/2;
    if(v[mijl]<x) mijl++;
    return mijl;
}

int main(){
    fi>>n;
    for(i=1;i<=n;i++) fi>>v[i];
    
    fi>>q;
    for(;q>0;q--){
                  fi>>k>>x;
                  
                  switch(k){
                  case 0 : fo<<bsearch0(x,1,n)<<"\n"; break;
                  case 1 : fo<<bsearch1(x,1,n)<<"\n"; break;
                  case 2 : fo<<bsearch2(x,1,n)<<"\n"; break;
                  }
                  
                 }
    
    fi.close();
    fo.close();
    return 0;
}