#include <cstdio>
int t,x,n,v[100000];
void read(){
	scanf("%d%d",&t,&x);
}
int solve(){
	int p=1,u=n,m;
	while (u-p>1){
		m=(p+u)/2;
		if (v[m]==x)
			return m;
		if (v[m]>x)
			u=m;
		if (v[m]<x)
			p=m+1;
	}
	if (v[p]==x)
		return p;
	if (v[u]==x)
		return u;
	if (t==1){
		if (v[p]<x)
			return p;
		else
			return p-1;
	}
	if (t==2){
		if (v[p]>x)
			return p;
		return u;
	}
	return -1;
}
void write(int i){
	printf("%d\n",i);
}
int main(){
	int i,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);
	for (i=1;i<=m;++i){
		read();
		write(solve());
	}	
}