#include <fstream>
#include <stdio.h>
using namespace std;
ofstream g("cautbin.out");
FILE * cautbin;
unsigned int a[100003],x,n,m,i,ls,ld,q,z;
int caut0(unsigned int ls,unsigned int ld,unsigned int x)
{
	if (ls>ld) return -1;
	else 
	{
		z=(ls+ld)/2;
		if (a[z]==x && a[z+1]!=x) return z;
		else
		{
			if (a[z]<=x) return caut0(z+1,ld,x);
			else return caut0(ls,z-1,x);
		}
	}
}
int caut1(unsigned int ls,unsigned int ld,unsigned int x)
{
	if (ls>ld)
	{
		if (a[z]<x) return z;
		else return (z-1);
	}
	else 
	{
		z=(ls+ld)/2;
		if (a[z]==x && a[z+1]!=x) return z;
		else
		{
			if (a[z]<=x) return caut1(z+1,ld,x);
			else return caut1(ls,z-1,x);
		}
	}
}
int caut2(unsigned int ls,unsigned int ld,unsigned int x)
{
	if (ls>ld) 
	{
		if (a[z]>x) return z;
		else return (z+1);
	}
	else 
	{
		z=(ls+ld)/2;
		if (a[z]==x && a[z-1]!=x) return z;
		else
		{
			if (a[z]<x) return caut2(z+1,ld,x);
			else return caut2(ls,z-1,x);
		}
	}
}
void citire()
{
	fscanf(cautbin,"%d",&n);
	for (i=1;i<=n;i++)
		fscanf(cautbin,"%u",&a[i]);
	fscanf(cautbin,"%d",&m);
	for (i=1;i<=m;i++)
	{
		fscanf(cautbin,"%d %u",&q,&x);
		if (q==0) g<<caut0(1,n,x)<<'\n';
		else 
		{
			if (q==1) g<<caut1(1,n,x)<<'\n';
			else g<<caut2(1,n,x)<<'\n';
		}
	}
}
int main()
{
	cautbin=fopen("cautbin.in","r");
	citire();
	g.close();
	return 0;
}