# include <stdio.h>
int n,m,a[100010],op,x,y,i;
void cautare(int op, int x)
{
	int st,dr,m;
	st=1; dr=n;
	while (st<=dr)
	{
		m=(st+dr)/2;
		if (a[m]>x) dr=m-1;
		else
			if (a[m]<x) st=m+1;
		else
			break;
	}
	y=m;
	if (op==0)
	{
		if (st>dr) printf("-1\n");
		else
		{
		while (a[m]==x) m++;
		printf("%d\n",m-1);
		}
	}
	if (op==1)
	{
		if (st>dr) printf("%d\n",st-1);
		else
		{
		while (a[m]==x) m++;
		printf("%d\n",m-1);
		}
	}
	if (op==2)
	{
		if (st>dr) printf("%d\n",st);
		else
		{
		while(a[m]==x) m--;
		printf("%d\n",m+1);
		}
	}
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d\n",&n);
	for (i=1; i<=n; i++)
		scanf("%d ",&a[i]);
	scanf("\n");
	scanf("%d\n",&m);
	for (i=1; i<=m; i++)
	{
		scanf("%d %d\n",&op,&x);
		cautare(op,x);
	}
	return 0;
}