#include<stdio.h>
using namespace std;
int x,tip,i,n,nri,a[100010];
int search(int x,int tip)
{
	int p,u,m;
	p=1;
	u=n;
	while(p<=u)
	{
		m=(p+u)/2;
		if(a[m]>x) u=m-1;
		else
		if(a[m]<x) p=m+1;
		else break;
	}
	if(tip==0)
	{
		if(p>u) return -1;
		while(a[m]==x) m++;
		return m-1;
	}
	else
	if(tip==1)
	{
		if(p>u) return p-1;
		while(a[m]==x) m++;
		return m-1;
	}
	else
	if(tip==2)
	{
		if(p>u) return p;
		else
		{
			while(a[m]==x) m--;
			return m+1;
		}
	}
}
int main()
{
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
	scanf("%d",&a[i]);
scanf("%d",&nri);
for(i=1;i<=nri;i++)
{
	scanf("%d",&tip);
	scanf("%d",&x);
	printf("%d\n",search(x,tip));
}
return 0;
}