#include<cstdio>

FILE *fin=fopen("cautbin.in","r");
FILE *fout=fopen("cautbin.out","w");

int a[100001],m,x,y,q,i,n;

int caut(int x){
	
	int ls=1,rs=n;
	int md;
	while(ls<=rs){
		md=(ls+rs)/2;
		if(a[md]==x) return md;
		else if(x>a[md]) ls=md+1;
		else rs=md-1;
	}
	return md;
	
}

int main(){
	
	fscanf(fin,"%d",&n);
	
	for(i=1;i<=n;i++)
		fscanf(fin,"%d",&a[i]);
	
	fscanf(fin,"%d",&m);
	
	while(m--){
		
		fscanf(fin,"%d%d",&q,&x);
		y=caut(x);
		if(q==0){
			if(a[y]==x)
				while(a[y]==a[y+1]) y++;
			else
				y=-1;
		}
		else if(q==1){
			if(a[y]==x)
				while(a[y]==a[y+1]) y++;
			else
				while(a[y]>x) y--;
		}
		else{
			if(a[y]==x)
				while(a[y]==a[y-1]) y--;
			else
				while(a[y]<x) y++;
		}
		
		fprintf(fout,"%d\n",y);
		
	}
	
	return 0;
	
}