#include<stdio.h>
int cauta( int *v, int p, int u, int x){
	if(p==u){
		if(x==v[p])
			return p;
		else
			return -1;
	}
	if(x<=v[(p+u)/2])
		return cauta(v,p,(p+u)/2,x);
	return cauta(v,(p+u)/2+1,u,x);
}
int cauta2( int *v, int p, int u, int x){
	if(p==u){
		if(v[p]<=x)
			return p;
		else
			return p-1;
	}
	if(x<=v[(p+u)/2])
		return cauta2(v,p,(p+u)/2,x);
	return cauta2(v,(p+u)/2+1,u,x);
}
int cauta3( int *v, int p, int u, int x){
	if(p==u){
		if(v[p]>=x)
			return p;
		else
			return p+1;
	}
	if(x<=v[(p+u)/2])
		return cauta3(v,p,(p+u)/2,x);
	return cauta3(v,(p+u)/2+1,u,x);
}
int main(){
	int v[100000],n,i,x,m,j,intr;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	scanf("%d",&m);
	for(j=0;j<m;j++){
		scanf("%d",&intr);
		scanf("%d",&x);
		if(intr==0)
			printf("%d\n",cauta(v,1,n,x));
		if(intr==1)
			printf("%d\n",cauta2(v,1,n,x));
		if(intr==2)
			printf("%d\n",cauta3(v,1,n,x));
	}
	return 0;
}