#include<stdio.h>
int cautare(int *v, int p, int u, int nr){
	if(p==u)
		if(v[p]==nr)
			return p;
		else
			return -1;
	if(nr<=v[(p+u)/2])
		return cautare(v,p,(p+u)/2,nr);
	return cautare(v,(p+u)/2+1,u,nr);
}
int cautare_mic(int *v, int p, int u, int nr){
	if(p==u)
		if(v[p]<=nr)
			return p;
		else
			return p-1;
	if(nr<=v[(p+u)/2])
		return cautare_mic (v,p,(p+u)/2,nr);
	return cautare_mic (v,(p+u)/2+1,u,nr);
}
int cautare_mare(int *v, int p, int u, int nr){
	if(p==u)
		if(nr<=v[p])
			return p;
		else
			return p+1;
	if(nr<=v[(p+u)/2])
		return cautare_mare (v,p,(p+u)/2,nr);
	return cautare_mare (v,(p+u)/2+1,u,nr);
}
int main(){
	int v[100008],nr,i,N,in,M;
	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);
	while(M--){
		scanf("%d%d",&in,&nr);
		if(in==0)
			printf("%d\n",cautare(v,1,N,nr));
		if(in==1)
			printf("%d\n",cautare_mic(v,1,N,nr));
		if(in==2)
			printf("%d\n",cautare_mare(v,1,N,nr));
	}
	return 0;
}