#include<stdio.h>
#include<string.h>
long a[1000005],n;
void cautbin(long x, long y, long st, long dr)
{
	int ok=0;
	long m;
	while (!ok && st<=dr)
	{
		m=(st+dr)/2;
		if (a[m]==y)
			if (x<=1) 
			{
				while (m<=n && a[m]==y) m++;
				printf("%i\n",m-1);
				ok=1;
			}
			else
			{
				while (m && a[m]==y) m--;
				printf("%i\n",m+1);
				ok=1;
			}
		else
			if (a[m]>y) 
				dr=m-1;
			else st=m+1;
	}
	if (!ok)
		switch(x)
		{
		case 0: printf("%s \n","-1");;
				break;
		case 1: printf("%i \n",dr);;
				break;
		case 2: printf("%i \n",st);
				break;
		}
}
int main()
{
	freopen ("cautbin.in","r",stdin);
	freopen ("cautbin.out","w",stdout);
	long i,m,x,y;
	scanf("%i",&n);
	for (i=1;i<=n;i++)
		scanf("%i",&a[i]);
	scanf("%i",&m);
	for (i=1;i<=m;i++)
	{
		scanf("%i%i",&x,&y);
		cautbin(x,y,1,n);
	}
	return 0;
}