#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,m,a[100005];
int i,j,x,y;
void citire(){
    f>>n;
    for(i=1;i<=n;i++){
        f>>a[i];
    }
}
int caut_binar1(int li,int ls,int y){
    int mij;
    if(li>ls)
        return -1;
    else{
        mij=li+(ls-li)/2;
        if(a[mij]==y){
            while(a[mij]==y)
                mij++;
            return mij-1;
        }
        else if(a[mij]<y){
            caut_binar1(mij+1,ls,y);
        }
        else
            caut_binar1(li,mij-1,y);
    }
}
int caut_binar2(int li,int ls,int y){
    int mij=ls;
    while(li<ls){
        mij=(li+ls)/2;
        if(a[mij]<=y)
            li=mij+1;
        else
            ls=mij;
    }
    mij=(li+ls)/2;
    if(a[mij]>y)
        mij--;
    return mij;
}
int caut_binar3(int li,int ls,int y){
    int mij=ls;
    while(li<ls){
        mij=(li+ls)/2;
        if(a[mij]<y)
            li=mij+1;
        else
            ls=mij;
    }
    mij=(li+ls)/2;
    if(a[mij]<y)
        mij++;
    return mij;
}
int main()
{
    citire();
    f>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        if(x==0){
            g<<caut_binar1(1,n,y)<<'\n';
        }
        else if(x==1)
            g<<caut_binar2(1,n,y)<<'\n';
        else
            g<<caut_binar3(1,n,y)<<'\n';
    }
    return 0;
}