#include<fstream.h>
int n,a[100100];
int bs0(int x)
{
	int l=1,i=0;
	while(l<n)
		l<<=1;
	while(l)
	{
		if(i+l<=n&&a[i+l]<=x)
			i+=l;
		l>>=1;
	}
	if(a[i]==x)
		return i;
	return -1;
}
int bs1(int x)
{
	int l=1,i=0;
	while(l<n)
		l<<=1;
	while(l)
	{
		if(i+l<=n&&a[i+l]<=x)
			i+=l;
		l>>=1;
	}
	return i;
}
int bs2(int x)
{
	int l=1,i=n;
	while(l<n)
		l<<=1;
	while(l)
	{
		if(i-l>0&&a[i-l]>=x)
			i-=l;
		l>>=1;
	}
	return i;
}
int main()
{
	int i,op,x,t;
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>a[i];
	f>>t;
	while(t--)
	{
		f>>op>>x;
		if(!op)
			g<<bs0(x);
		else
			if(op==1)
				g<<bs1(x);
			else
				g<<bs2(x);
		g<<'\n';
	}
	return 0;
}