#include <cstdio>
int n,m,v[100050],val;

void caut(int st,int dr)
{
	if (st==dr)
	{
		if (v[st]==val)
			printf("%d\n",st);
		else
			printf("%d\n",-1);
		return;
	}
	int m=(st+dr)/2;
	if (v[m]==val)
	{
		if (v[m+1]==val)
			caut(m+1,dr);
		else
			printf("%d\n",m);
		return;
	}
	if (v[m]>val)
		caut(st,m);
	else
		caut(m+1,dr);
}

void cautmic(int st,int dr)
{
	if (st==dr)
	{
		printf("%d\n",st-1);
		return;
	}
	int m=(st+dr)/2;
	if (v[m]==val)
	{
		if (v[m+1]==val)
			cautmic(m+1,dr);
		else
			printf("%d\n",m);
		return;
	}
	if (v[m]<val)
		cautmic(m+1,dr);
	else
		cautmic(st,m);
}

void cautmare (int st,int dr)
{
	if (st==dr)
	{
		printf("%d\n",st);
		return;
	}
	int m=(st+dr)/2;
	if (v[m]>=val)
		cautmare(st,m);
	else
		cautmare(m+1,dr);
}


int main()
{
	freopen ("cautbin.in","r",stdin);
	freopen ("cautbin.out","w",stdout);
	int x;
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%d",&v[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&val);
		if (x==0)
			caut(1,n);
		if (x==1)
		{
			if (val==v[n])
			{
				printf("%d\n",n);
				continue;
			}
			cautmic(1,n);
		}
		if (x==2)
		{
			if (val==v[1])
			{
				printf("%d\n",1);
				continue;
			}
			cautmare(1,n);
		}
	}
	return 0;
}