#include <fstream>

using namespace std;
int v[100005];
int n;
int bsleft(int x){
    int st=1,dr=n,mij,last=-1;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]<=x){
            st=mij+1;
            last=mij;
        } else {
            dr=mij-1;
        }
    }
    return last;
}
int bsright(int x){
    int st=1,dr=n,mij,last=-1;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]<x){
            st=mij+1;
        } else {
            dr=mij-1;
            last=mij;
        }
    }
    return last;
}

int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int x,t,m,i,poz;
    fin>>n;
    for(i=1;i<=n;++i){
        fin>>v[i];
    }
    fin>>m;
    for(i=1;i<=m;++i){
        fin>>t>>x;
        if(t==0){
            poz=bsleft(x);
            if(v[poz]==x){
                fout<<poz<<"\n";
            } else {
                fout<<"-1"<<"\n";
            }
        } else if(t==1){
            fout<<bsleft(x)<<"\n";
        } else {
            fout<<bsright(x)<<"\n";
        }
    }

    return 0;
}