#include<stdio.h>
FILE*f=fopen("cautbin.in","r");
FILE*g=fopen("cautbin.out","w");
int nr,m,p,u,x,n,y,v[100001],i;
int main() {
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&v[i]);
	fscanf(f,"%d",&y);
	for(i=1;i<=y;i++){
		p=1;
		u=n;
		fscanf(f,"%d%d",&nr,&x);
		if(nr==0){
			while(p<=u){
				m=(p+u)/2;
				if(v[m]<=x)
					p=m+1;
				else
					u=m-1;
			}
			m=(p+u)/2;
			if(v[m]>x)
				m--;
			if(v[m]==x)
				fprintf(g,"%d\n",m);
			else
				fprintf(g,"-1\n");
		}else
			if(nr==1){
				while(p<u){
					m=(p+u)/2;
					if(v[m]<=x)
						p=m+1;
					else
						u=m;
				}
				m=(p+u)/2;
				if(v[m]>x)
					m--;
				fprintf(g,"%d\n",m);
			}else{
				while(p<u){
					m=(p+u)/2;
					if(v[m]<x)
						p=m+1;
					else
						u=m;
				}
				m=(p+u)/2;
				if(v[m]<x)
					m++;
				fprintf(g,"%d\n",m);
			}
	}	
	fclose(g);
	fclose(f);
	return 0;
}