#include<stdio.h>
long n,x[200000],y,i,m,l,poz;
int cb (long val)
{
	int st,dr,med,last=-1;
	st=1;
	dr=n;
	while (st<=dr)
	{
		med=(st+dr)/2;
		if (val>=x[med])
		{
			last=med;
			st=med+1;
		}
		else
			dr=med-1;
	}
	return last;
}
int cb2 (long val)
{
	int st,dr,med,last=-1;
	st=1;
	dr=n;
	while (st<=dr)
	{
		med=(st+dr)/2;
		if (val<=x[med])
		{
			last=med;
			dr=med-1;
		}
		else
			st=med+1;
	}
	return last;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
		scanf("%ld",&x[i]);
	scanf("%ld",&m);
	for (i=1;i<=m;i++)
	{
		scanf("%ld%ld",&l,&y);
		poz=cb(y);
		if (l==0)
          if(x[poz]==y)		
			printf("%ld\n",poz);
		  else
			printf("-1");
		if (l==1)
			printf("%ld\n",poz);	
		if (l==2)
			printf("%ld\n",cb2(y));
	}
}