#include<stdio.h>
FILE *f=fopen("cautabin.in","r"),*g=fopen("cautabin.out","w");
long int n,m;
int v[100010];

int bsh0(long int st,long int sf,long int val){
long int mij;
	
	while(st<=sf){
		mij=(st+sf)/2;
		if(v[mij]<=val){
			st=mij+1;
		}
		else {
			sf=mij-1;
		}
	}
	mij=(st+sf)/2;
	if(v[mij]>val){mij--;}
	else if(v[mij]==val){
		return mij;
	}
	return -1;
}

int bsh1(long int st,long int sf,long int val){
long int mij;
	while(st<sf){
		mij=(st+sf)/2;
		if(v[mij]>val){sf=mij;}
		else {st=mij+1;}
	}
	mij=(st+sf)/2;
	if(v[mij]>val){mij--;}
		return mij;
}

int bsh2(long int st,long int sf,long int val){
long int mij;
	while(st<sf){
		mij=(st+sf)/2;
		if(v[mij]<val){st=mij+1;}
		else {sf=mij;}
	}
	mij=(st+sf)/2;
	if(v[mij]<val){mij++;}
	return mij;
	
}

void read(){
long int i,t,x;
	fscanf(f,"%ld\n",&n);
	for(i=1; i<=n; i++){
		fscanf(f,"%d ",&v[i]);
	}
	fscanf(f,"%ld\n",&m);
	for(i=1; i<=m; i++){
		fscanf(f,"%ld %ld\n",&t,&x);
		if(t==0){
			fprintf(g,"%ld\n",bsh0(1,n,x));
		}
		else if(t==1){
			fprintf(g,"%ld\n",bsh1(1,n,x));
		}
		else{
			fprintf(g,"%ld\n",bsh2(1,n,x));
		}
	}
}

int main(){
	read();
return 0;
}