#include<fstream>
using namespace std;
#define nn 100001
int m,n,a[nn];
int cauta0(int st,int dr,int x){
    int mid;
    while(st<=dr){
     mid = st+ (dr-st)/2;
    if(a[mid]<=x)
        st = mid+1;
    else
        dr = mid-1;
    }
    if(a[mid]>x)--mid;
    if(a[mid]==x)return mid;
    return -1;
}
int cauta1(int st,int dr,int x){
    int mid;
    while(st<dr){
        mid = st+ (dr-st)/2;
        if(a[mid]<=x)
            st= mid+1;
        else
            dr= mid;
    }
    mid = st+ (dr-st)/2;
    if(a[mid]>x)--mid;
    return mid;
}
int cauta2(int st,int dr,int x){
    int mid;
    while(st<dr){
            mid= st+(dr-st)/2;
        if(a[mid]<x)
            st = mid+1;
        else
            dr= mid;
    }
    mid = st+ (dr-st)/2;
    if(a[mid]<x)
        ++mid;
    return mid;
}
void citire(){
    int i,x,y;
    ifstream fin("cautbin.in");
    FILE *f=fopen("cautbin.out","w");
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>a[i];
    fin>>m;
    for(i=1;i<=m;++i){
        fin>>x>>y;
        if(x==0)
            fprintf(f,"%d\n",cauta0(1,n,y));
        if(x==1)
            fprintf(f,"%d\n",cauta1(1,n,y));
        if(x==2)
            fprintf(f,"%d\n",cauta2(1,n,y));
    }
}
int main(){
    citire();
    return 0;
}