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