#include <fstream>

using namespace std;
int n,v[100001];
int cb1(int x){
    int poz = -1,st=1,dr=n;
    while(st<=dr){
        int mij = (st+dr)/2;
        if(v[mij]==x)
            poz = max(poz,mij),st=mij+1;
        else if(v[mij]<x)
            st=mij+1;
        else
            dr = mij-1;

    }
    return poz;
}
int cb2(int x){
    int poz = -1,st=1,dr=n;
    while(st<=dr){
        int mij = (st+dr)/2;
        if(v[mij]<=x)
            poz = max(poz,mij),st=mij+1;
        else
            dr = mij-1;
    }
    return poz;
}
int cb3(int x){
    int poz = 1000000000,st=1,dr=n;
    while(st<=dr){
        int mij = (st+dr)/2;
        if(v[mij]>=x)
            poz = min(poz,mij),dr=mij-1;
        else
            st = mij+1;
    }
    if(poz==1000000000)
        return -1;
    return poz;
}
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main(){
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    int m; fin>>m;
    while(m--){
        int op,x; fin>>op>>x;
        if(op==0){
            fout<<cb1(x)<<'\n';
        }
        else if(op==1){
            fout<<cb2(x)<<'\n';
        }
        else
            fout<<cb3(x)<<'\n';
    }

    return 0;
}