#include <stdio.h>

FILE*f = fopen("cautbin.in","r");
FILE*g = fopen("cautbin.out","w");

int N, M,i,m;
int A[100002];
int p,u;
int nr, x;

int main() {
	
	fscanf(f,"%d",&N);
	for(i=1;i<=N;i++){
		fscanf(f,"%d",&A[i]);
	}
	fscanf(f,"%d",&M);
	
	for(i=1;i<=M;i++){
		fscanf(f,"%d %d",&nr,&x);
		
		if (nr==0) {
			
			p=1; u=N;
			while (p<=u){
				m = p + (u-p)/2;
				if(A[m]>x)
					u=m-1;
				else
					p=m+1;
			}
			if(A[u]==x)
				fprintf(g,"%d\n",u);
			else
				fprintf(g,"-1\n");
			
		}
		if (nr==1) {
			p=1; u=N;
			while (p<=u){
				m = p + (u-p)/2;
				if(A[m]<=x)
					p=m+1;
				else
					u=m-1;
			}
			fprintf(g,"%d\n",u);
		}
		if (nr==2) {
			p=1; u=N;
			while (p<=u){
				m = p + (u-p)/2;
				if(A[m]>=x)
					u=m-1;
				else
					p=m+1;
			}
			fprintf(g,"%d\n",p);
		}
	}
	
	fclose(f);
	fclose(g);
	return 0;
}