#include <cstdio>


int a[100005],n;

int ctb(int mod,int x,int st, int dr){
    int mid=(st+dr)/2;
    if(mod==0){
        if(st==dr){
            if(x==a[st]) return st;
                else return -1;
        }
        if(x>a[mid]) return ctb(0,x,mid+1,dr);
            else return ctb(0,x,st,mid);
    }
     if(mod==1){
        if(st+1==dr){
            if(x>=a[dr]) return dr;
            if(x>=a[st]) return st;
        }
        if(x>=a[mid]) return ctb(1,x,mid,dr);
        if(x<=a[mid]) return ctb(1,x,st,mid);
    }
    if(mod==2){
        if(st+1==dr){
            if(x<=a[st]) return st;
            if(x<=a[dr]) return dr;

        }
        if(x<=a[mid]) return ctb(2,x,st,mid);
        if(x>=a[mid]) return ctb(2,x,mid,dr);

    }

}

int main (){
    int i,m,x,mod;
    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",&m);
    for(i=1;i<=m;++i){
        scanf("%d%d",&mod,&x);
        printf("%d\n",ctb(mod,x,1,n));
    }
}