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