# include <stdio.h>
int n,m,a[100010],op,x,y,i;
void cautb0(int x,int st,int dr)
{
	if (st>dr) printf("-1\n");
	else
	{
	int m=st+(dr-st)/2;
	if (a[m]==x && (a[m+1]>x || m==n)) printf("%d\n",m);
	else
	if (a[m]>x)
		cautb0(x,st,m);
	else
		cautb0(x,m+1,dr);
	}
}

int cautb1(int x, int st, int dr)
{
	if (st>dr) printf("%d\n",dr);
	else
	{
	int m=st+(dr-st)/2;
	if (a[m]==x && (a[m+1]>x || m==n)) printf("%d\n",m);
	else
		if (a[m]<=x && (a[m+1]>x || m==n)) printf("%d\n",m);
	else
	if (a[m]>x)
		cautb1(x,st,m);
	else
		cautb1(x,m+1,dr);
	}
}

int cautb2(int x, int st, int dr)
{
	if (st>dr) printf("%d\n",dr);
	else
	{
	int m=st+(dr-st)/2;
	if (a[m]==x && (a[m-1]<x || m==1)) printf("%d\n",m);
	else
		if (a[m]>=x && (a[m-1]<x || m==1)) printf("%d\n",m);
	else
	if (a[m]>=x)
		cautb2(x,st,m);
	else
		cautb2(x,m+1,dr);
	}
}
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);
		if (op==0)
		{
		    cautb0(x,1,n);
		}
		if (op==1)
		{
			cautb1(x,1,n);
		}
		if (op==2)
		{
			cautb2(x,1,n);
		}
	}
	return 0;
}