#include <cstdio>
#define  BM  100005
int s[BM],n;
int zero(int a,int ls,int ld){
    int m;
	if(ls>=ld-1){
		if(s[ld]==a)return ld;
		if(s[ls]==a)return ls;
		return -1;
	}
	m=(ls+ld)/2;
	if(s[m]<=a)return zero(a,m,ld);
	return zero(a,ls,m);
}

int unu(int a,int ls,int ld){
    int m;
	if(ls>=ld-1){
		if(a>=s[ld])return ld;
		return ls;
	}
	m=(ls+ld)/2;
	if(s[m]<=a) return unu(a,m,ld);
	return unu(a,ls,m);
}

int doi(int a,int ls,int ld){
    int m;
	if(ls>=ld-1){
		if(a<=s[ld])return ld;
		return ls;
	}
	m=(ls+ld)/2;
	if(s[m]<a)return doi(a,m,ld);
	return doi(a,ls,m);
}

int main(){
    int i,m,o,a;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&s[i]);
    scanf("%d",&m);
    for(i=1;i<=m;++i){
        //fprintf(stderr,"%d ",i);
        scanf("%d %d",&o,&a);
        if(o==0) printf("%d\n",zero(a,1,n));
        else if(o==1) printf("%d\n",unu(a,1,n));
        else printf("%d\n",doi(a,1,n));

    }
    return 0;
}