#include<cstdio>
using namespace std;
FILE *f=fopen("cautbin.in","r"), *g=fopen("cautbin.out","w");
int a[100001];
int bin0(int x, int y, int k)
{
	int m;
	while(x<=y)
	{
		m=(x+y)/2;
		if(a[m]>=k)
			x=m+1;
		else y=m-1;
	}
	m=(x+y)/2;
	if(a[m]>k) m--;
	if(a[m]==k) return m;
	return -1;
}
int bin1(int x, int y, int k)
{
	int m;
	while(x<y)
	{
		m=(x+y)/2;
		if(a[m]>=k)
			x=m+1;
		else y=m;
	}
	m=(x+y)/2;
	if(a[m]>k) m--;
	return m;
}
int bin2(int x, int y, int k)
{
	int m;
	while(x<y)
	{
		m=(x+y)/2;
		if(a[m]<k)
			x=m+1;
		else y=m;
	}
	m=(x+y)/2;
	if(a[m]<k) m++;
	return m;
}
int main()
{
	int n,m,i,intr,x;
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&a[i]);
	fscanf(f,"%d",&m);
	while(m --)
	{
		fscanf(f,"%d %d",&intr,&x);
		if(intr==0) fprintf(g,"%d\n",bin0(1,n,x));
		else if(intr==1) fprintf(g,"%d\n",bin1(1,n,x));
		else if(intr==2) fprintf(g,"%d\n",bin2(1,n,x));
	}
	return 0;
}