#include <stdio.h>
#define N 100001
int v[N],n,m,a,orig;
int cautbin1(int x){
	int st=1,dr=n,m;
	while(st<dr){
		m=(st+dr)>>1;
		if(v[m]<x) st=m+1;
		else dr=m;
	}
	if(v[st]<=x) return st;
	return st-1;
}
int cautbin0(int x){
	int st=1,dr=n,m;
	if(v[n]==x) return n;
	while(st<dr){
		m=(st+dr)>>1;
		if(v[m]<=x) st=m+1;
		else dr=m;
	}
	if(v[st-1]!=x) return -1;
	return st-1;
}
int cautbin2(int x){
	int st=1,dr=n,m;
	while(st<dr){
		m=(st+dr)>>1;
		if(v[m]<=x) st=m+1;
		else dr=m;
	}
	if(v[st]==x) return st;
	if(v[st-1]>=x) return st-1;
	return st;
}
int main(){
	int i,x;
	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(i=1;i<=m;i++){
		scanf("%d%d",&a,&x);
		orig=x;
		if(a==1) printf("%d\n",cautbin1(x));
		else if(a==0) printf("%d\n",cautbin0(x));
		else printf("%d\n",cautbin2(x));
	}
	return 0;
}