#include<stdio.h>
#define N 100001
FILE *f1,*f2;
long a,b,i,j,n,m,t,x,v[N];
long bs(long z){
	t=1;
	while((t<<=1) < n);
	t>>=1;
	for(i=0;t;t>>=1){
		if(i+t<n&&v[i+t]<=z){
			i+=t;
		}
	}
	return i;
}
int main(){
	f1=fopen("cautbin.in","r");
	f2=fopen("cautbin.out","w");
	fscanf(f1,"%ld",&n);
	for(i=1;i<=n;fscanf(f1,"%ld",&v[i]),i++);
	fscanf(f1,"%ld",&m);
	for(j=1;j<=m;j++){
		fscanf(f1,"%ld%ld",&a,&x);
		b=bs(x);
		if(a==0){
			if(v[b]!=x){
				b=-1;
			}
			fprintf(f2,"%ld\n",b);
		}
		if(a==1){
			while(v[b]>x && b>=1){
				b--;
			}
			if(v[b+1]<=x){
				b++;
			}
			if(v[b+1]<=x){
				b++;
			}
			fprintf(f2,"%ld\n",b);
		}
		if(a==2){
			while(v[b]<x && b<=n){
				b++;
			}
			if(v[b-1]>=x){
				b--;
			}
			if(v[b-1]>=x){
				b--;
			}
			fprintf(f2,"%ld\n",b);
		}
	}
	return 0;
}