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