#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n;
int v[100001];
int cautbin0(int x){
    int mij,rh=n,lf=1;
    while(lf<rh){
        mij=(lf+rh)/2;
        if(x<v[mij]||(x==v[mij]&&v[mij]!=v[mij+1]))rh=mij;
        else lf=mij+1;
    }
    if(x==v[lf])return lf;
    return -1;
}
int cautbin1(int x){
    int mij,rh=n,lf=1;
    while(lf<rh){
        mij=(lf+rh)/2;
        if(x<v[mij]||(x==v[mij]&&v[mij]!=v[mij+1]))rh=mij;
        else lf=mij+1;
    }
    if(v[lf]!=x)return lf-1;
    return lf;
}
int cautbin2(int x){
    int mij,rh=n,lf=1;
    while(lf<rh){
        mij=(lf+rh)/2;
        if(x<=v[mij])rh=mij;
        else lf=mij+1;
    }
    if(v[lf]!=x)return lf+1;
    return lf;
}
int main(){
    int m,i,p,x;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(i=1;i<=m;i++){
        fin>>p>>x;
        if(p==0)fout<<cautbin0(x)<<'\n';
        if(p==1)fout<<cautbin1(x)<<'\n';
        if(p==2)fout<<cautbin2(x)<<'\n';

    }
    fin.close();
    fout.close();
    return 0;
}