#include<stdio.h>
int n,m;
int a[100002];

int bs0(int x)
{
int st,dr,med,last=-1;
st=1;
dr=n;
while(st<=dr)
{
	med=(st+dr)/2;
	if(x>=a[med])
	{
		last=med;
		st=med+1;
	}
	else
	dr=med-1;

}
return last;
}

int bs1(int x)
{
int st,dr,med,last=-1;
st=1;
dr=n;
while(st<=dr)
{
	med=(st+dr)/2;
	if(x<=a[med])
	{
		last=med;
		dr=med-1;
	}
	else
	st=med+1;

}
return last;
}


int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
int i,x,tip,poz,t;
scanf("%d",&n);
for(i=1;i<=n;i++)
	scanf("%d",&a[i]);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
	scanf("%d%d",&tip,&x);
	if(tip==0)
	{
		poz=bs0(x);
		if(a[poz]!=x)
			printf("-1\n");
		else
			printf("%d\n",poz);
	}
	else
		if(tip==1)
		{
			poz=bs0(x);
			printf("%d\n",poz);
		}
		else
		{
			poz=bs1(x);
			printf("%d\n",poz);
		}
}
		return 0;
}