#include<cstdio>
using namespace std;
int i, n, a[100001], nrOperatii, op, val;
int cauta0(){
    int st=1, dr=n, mij, sol=-1;
    while (st<=dr) {
        mij=st+(dr-st)/2;
        if (a[mij]<=val) {if (a[mij]==val) sol=mij; st=mij+1;}
            else dr=mij-1;
    }
    return sol;
}
int cauta1(){
    int st=1, dr=n, mij, sol=-1;
    while (st<=dr) {
        mij=st+(dr-st)/2;
        if (a[mij]<=val) {sol=mij; st=mij+1;}
            else dr=mij-1;
    }
    return sol;
}
int cauta2(){
    int st=1, dr=n, mij, sol=-1;
    while (st<=dr) {
        mij=st+(dr-st)/2;
        if (a[mij]>=val) {sol=mij; dr=mij-1;}
            else st=mij+1;
    }
    return sol;
}
int main(){
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n); for (i=1;i<=n;i++) scanf("%d", &a[i]);
    scanf("%d", &nrOperatii);
    for (i=1;i<=nrOperatii;i++) {
        scanf("%d%d", &op, &val);
        if (op==0) printf("%d\n", cauta0());
        if (op==1) printf("%d\n", cauta1());
        if (op==2) printf("%d\n", cauta2());
    }
    return 0;
}