#include<stdio.h>
using namespace std;
int n,m,j,f,x,v[100000];
int cautbin0(int x)
{
	int i,pas=1<<16;
	for(i=0;pas!=0;pas/=2)
		if(i+pas<=n && v[i+pas]<=x)
			i+=pas;
	if(v[i]!=x)
			return -1;
	return i;
}
int cautbin1(int x)
{
	int i,pas=1<<16;
	for(i=0;pas!=0;pas/=2)
		if(i+pas<=n && v[i+pas]<=x)
			i+=pas;
	return i;
}
int cautbin2(int x)
{
	int i,pas=1<<16;
	for(i=0;pas!=0;pas/=2)
		if(i+pas<=n && v[i+pas]<x)
			i+=pas;
	return 1+i;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(j=1;j<=n;j++)
		scanf("%d",&v[j]);
	scanf("%d",&m);
	for(j=1;j<=m;j++)
		{
		 scanf("%d%d",&f,&x);
		 if(f==0)printf("%d\n",cautbin0(x));
		 if(f==1)printf("%d\n",cautbin1(x));
		 if(f==2)printf("%d\n",cautbin2(x));
		}	
	return 0;
}