#include <stdio.h>
#define P 1<<17
int n,v[P],teste;
void read()
{
	scanf("%d\n",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d",&v[i]);
	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;
}