#include <stdio.h>
#define P 1<<17
int n,v[P],r,teste;
void read()
{
	scanf("%d\n",&n);
	int nr=0,ok=1;
	char x;
	while (ok)
	{
		scanf("%c",&x);
		if (x=='\n')
			ok=0;
		if (x>='0' && x<='9')
			nr=nr*10+x-'0';
		if (x==' ' && 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;
}