#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int NMAX=100001;
int v[NMAX];
int cerinta0(int nr,int n){
    int st=1,dr,mij;
    st=1;
    dr=n+1;
    while(dr-st>1){
        mij=st+(dr-st)/2;
        if(v[mij]<=nr){
            st=mij;
        }
        else{
            dr=mij;
        }
    }
    if(v[dr-1]==nr){
        return st;
    }
    else{
        return -1;
    }
}
int cerinta1(int nr,int n){
    int st,dr,mij;
    st=1;
    dr=n+1;
    while(dr-st>1){
        mij=st+(dr-st)/2;
        if(v[mij]<=nr){
            st=mij;
        }
        else{
            dr=mij;
        }
    }
    return st;
}
int cerinta2(int nr,int n){
    int st,dr,mij;
    st=0;
    dr=n;
    while(dr-st>1){
       mij=st+(dr-st)/2;
        if(v[mij]>=nr){
            dr=mij;
        }
        else{
            st=mij;
        }
    }
    return dr;
}
int main()
{
    int n,m,cerinta,nr,ans;
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i];
    }
    fin>>m;
    for(int i=1;i<=m;i++){
        fin>>cerinta>>nr;
        if(cerinta==0){
            fout<<cerinta0(nr,n)<<'\n';
        }
        else if(cerinta==1){
            fout<<cerinta1(nr,n)<<'\n';
        }
        else{
            fout<<cerinta2(nr,n)<<'\n';
        }
    }
    return 0;
}