#include <stdio.h>
#define N 1<<20
#define P 1<<17
char t[N];
int n,v[P],r,teste;
void read()
{
	scanf("%d\n",&n);
	fgets(t+1,N,stdin);
	int i,nr=0;
	for (i=1; (t[i]>='0' && t[i]<='9') || t[i]==' '; i++)
	{
		if (t[i]>='0' && t[i]<='9')
			nr=nr*10+t[i]-'0';
		if (t[i]==' ' && nr)
		{
			v[++r]=nr;
			nr=0;
		}
	}
	if (nr)
		v[++r]=nr;
	scanf("%d",&teste);
}
int cbin(int x)
{
	int i,step;
	for (step=1; step<=n; step<<=1);
	for (i=0; step; step>>=1)
		if (i+step<=n && v[i+step]<=x)
			i+=step;
	if (v[i]==x)
		return i;
	return -1;
}
int cbin2(int x)
{
	int i,step;
	for (step=1; step<=n; step<<=1);
	for (i=0; step; step>>=1)
		if (i+step<=n && v[i+step]<=x)
			i+=step;
	if (v[i]>x)
		--i;
	return i;
}
int cbin3(int x)
{
	int i,step;
	for (step=1; step<=n; step<<=1);
	for (i=0; step; step>>=1)
		if (i+step<=n && v[i+step]<x)
			i+=step;
	return i+1;
}
void solve()
{
	int i,x,y;
	for (i=1; i<=teste; i++)
	{
		scanf("%d%d",&x,&y);
		if (x==0)
			printf("%d\n",cbin(y));
		if (x==1)
			printf("%d\n",cbin2(y));
		if (x==2)
			printf("%d\n",cbin3(y));
	}
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	read();
	solve();
	return 0;
}