#include<stdio.h>
int i,v[100100],N,n,x,val,poz;
int bin (int a)
{
	int in,sf,mij;
	in=1;
	sf=n;
	while(in<=sf)
	{
		mij=(in+sf)/2;
		if(a==v[mij])
			return mij;
		else
			if(a>v[mij])
				in=mij+1;
			else
				sf=mij-1;
	}
	return mij;
}
int main ()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	scanf("%d",&N);
	for(i=1;i<=N;i++)
	{
		scanf("%d%d",&val,&x);
		poz=bin(x);
		if(val==0)
		{
			if(x==v[poz])
			{
			while(x==v[poz+1])
				poz++;
			}
			else
				poz=-1;
			printf("%d\n",poz);
		}
		else
			if(val==1)
			{
				while(x>=v[poz+1])
					poz++;
				printf("%d\n",poz);
			}
			else
			{
				while(x<=v[poz-1])
					poz--;
				printf("%d\n",poz);
			}
	}
	return 0;
}