#include<cstdio>
#define NM 100005
int v[NM],N;
int caut0(int x)
{
	int p=1,u=v[0],m,pok=-1;
	while (p<=u)
	{
		m=(p+u)>>1;
		if (x>=v[m])
		{
			pok=m;
			p=m+1;
		}
		else
			u=m-1;
	}
	if (x==v[pok])
	return pok;
	return -1;
}
int cauta1(int x)
{
	int p=1,u=v[0],m,pok=-1;
	while (p<=u)
	{
		m=(p+u)>>1;
		if (x>=v[m])
		{
			pok=m;
			p=m+1;
		}
		else
			u=m-1;
	}
	return pok;
}
int cauta2(int x)
{
	int p=1,u=v[0],m,pok=-1;
	while (p<=u)
	{
		m=(p+u)>>1;
		if (x<=v[m])
		{
			pok=m;
			u=m-1;
		}
		else
			p=m+1;
	}
	return pok;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&N);
	int x,op;
	for (int i=1; i<=N; ++i)
		scanf("%d",&v[i]);
	v[0]=N;
	scanf("%d",&N);
	while (N--)
	{
		scanf("%d%d",&op,&x);
		if (op==0)
		{
			
				printf("%d\n",caut0(x));
			continue;
		}
		if (op==1)
		{
			printf("%d\n",cauta1(x));
			continue;
		}
		printf("%d\n",cauta2(x));
	}
	return 0;
}