#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;   
}