#include<stdio.h>
int n,m;
int v[100010];
void citire()
{
	int i;
	scanf("%d",&n);
	for(i=1; i<=n; i++)
		scanf("%d",&v[i]);
	scanf("%d",&m);
}
int caut(int x)
{
	int p=1,u=n,mij;
	while(p<u)
	{
		mij=(p+u)>>1;
		if(x<=v[mij])
			u=mij;
		else
			p=mij+1;
	}
	return p;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	citire();
	int i,aux,x,r;
	for(i=0; i<m; i++)
	{
		scanf("%d%d",&aux,&x);
		r=caut(x);
		if(aux==0)
		{
			if(v[r]!=x)
				r=-1;
			else
				while(v[r+1]==x)
					r++;
		}
		else
		if(aux==1)
		{
			while(v[r]>x)
				r--;
		}
		else
			while(v[r]<x)
				r++;
		printf("%d\n",r);
	}
	return 0;
}