#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int v[100010];
int n,m,st,dr,mj,ok,nr,x;

int cb0(int a){
    st=0;
    dr=n+1;
    ok=1;
    while((dr-st)>1){
        mj=(st+dr)/2;
        if(v[mj]<=a) st=mj;
        else dr=mj;
        if(v[mj]==a) ok=0;
    }
    if(ok) return -1;
    else return mj;
}

int cb1(int a){
    st=0;
    dr=n+1;
    while((dr-st)>1){
        mj=(st+dr)/2;
        if(v[mj]<=a) st=mj;
        else dr=mj;
    }
    return st;
}

int cb2(int a){
    st=0;
    dr=n+1;
    while((dr-st)>1){
        mj=(st+dr)/2;
        if(v[mj]>=a) dr=mj;
        else st=mj;
    }
    return dr;

}

int main(){
    fin>>n;
    for(int i=1;i<=n;++i) fin>>v[i];
    fin>>m;
    while(m){
        --m;
        fin>>nr>>x;
        if(nr==0) fout<<cb0(x)<<'\n';
        if(nr==1) fout<<cb1(x)<<'\n';
        if(nr==2) fout<<cb2(x)<<'\n';
    }



    return 0;
}