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