#include<fstream.h>
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
long a[100005],n,i,j,x,m;
long cautx(long i,long j)
{long m;
	m=i+(j-i)/2;
	while (x!=a[m]&&i!=j)
		{if (a[m]<x) i=m+1;
		 if (a[m]>x) j=m-1;
		 m=i+(j-i)/2;}
	if (a[m]==x) return m;
		else return -1;
	}
long cautmin(long i,long j)
{long m;
	m=i+(j-i)/2;
	while (i<j)
		{if (a[m]<x) i=m+1;
		 if (a[m]>x) j=m-1;
		 m=i+(j-i)/2;}
	return m-1;
	}
long cautmax(long i,long j)
{long m;
	m=i+(j-i)/2;
	while (i<j)
		{if (a[m]<x) i=m+1;
		 if (a[m]>x) j=m-1;
		 m=i+(j-i)/2;}
	return m;
	}
int s;
int main()
	{long k;
	 fin>>n;
	 for (i=1;i<=n;i++)
		fin>>a[i];
	 fin>>m;
	 for (k=1;k<=m;k++)
	 {fin>>s>>x;
		if (s==0) fout<<cautx(1,n)<<'\n';
		if (s==1) fout<<cautmin(1,n)<<'\n';
		if (s==2) fout<<cautmax(1,n)<<'\n';}
fout.close();
return 0;}