#include <stdio.h>
#define Q 100005
int v[Q],n;
int caut0(int x)
{
	int st=1, dr=n,m;
	while(st!=dr)
	{
		m=(st+dr+1)/2;
		if(x>=v[m])
			st=m;
		else
			dr=m-1;
	}
	if(x==v[st])
		return st;
	return -1;
}
int caut1(int x)
{
	int st=1, dr=n,m;
	while(st!=dr)
	{
		m=(st+dr)/2;
		if(x<=v[m])
			dr=m;
		else
			st=m+1;
	}
	if(v[st]>x)
		--st;
	return st;
}
int caut2(int x)
{
	int st=1, dr=n,m;
	while(st!=dr)
	{
		m=(st+dr)/2;
		if(x<=v[m])
			dr=m;
		else
			st=m+1;
	}
	if(v[st]<x)
		++st;
	return st;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	int m,i,tip,x;
	scanf("%d",&n);
    for (i=1; i<=n; i++)
		scanf("%d",&v[i]);
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d%d",&tip,&x);
		if(tip==0)
			printf("%d\n",caut0(x));
		if(tip==1)
			printf("%d\n",caut1(x));
		if(tip==2)
			printf("%d\n",caut2(x));
	}
	return 0;
}