#include<stdio.h>
int cautare(int *v, int p, int u, int nr){
    if(p==u)
        if(v[p]==nr)
            return p;
        else
            return -1;
    if(nr<=v[(p+u)/2])
        return cautare(v,p,(p+u)/2,nr);
    return cautare(v,(p+u)/2+1,u,nr);
}
int cautare_mic(int *v, int p, int u, int nr){
    if(p==u)
        if(v[p]<=nr)
            return p;
        else
            return p-1;
    if(nr<=v[(p+u)/2])
        return cautare_mic (v,p,(p+u)/2,nr);
    return cautare_mic (v,(p+u)/2+1,u,nr);
}
int cautare_mare(int *v, int p, int u, int nr){
    if(p==u)
        if(nr<=v[p])
            return p;
        else
            return p+1;
    if(nr<=v[(p+u)/2])
        return cautare_mare (v,p,(p+u)/2,nr);
    return cautare_mare (v,(p+u)/2+1,u,nr);
}
int main(){
    int v[100008],nr,i,N,in,M;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&N);
    for(i=1;i<=N;++i)
        scanf("%d",&v[i]);
    scanf("%d",&M);
    while(M--){
        scanf("%d%d",&in,&nr);
        if(in==0)
            printf("%d\n",cautare(v,1,N,nr));
        if(in==1)
            printf("%d\n",cautare_mic(v,1,N,nr));
        if(in==2)
            printf("%d\n",cautare_mare(v,1,N,nr));
    }
    return 0;
}