#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;
		if (x>a[(st+dr)/2]) st=(st+dr)/2;
	}
return -1;
}		

int czero (int x)
{
	poz=cautare(x);
	if (poz==-1) return -1;
	else 
		while (a[poz]==x) poz++;
return poz-1;
}

int cunu (int x)
{
	poz=cautare(x);
	if (poz!=-1) 
	{
		while (a[poz]==x) poz++;
		return poz-1;
	}
else
{
	poz=1;
	while (a[poz]<x) poz++;
	return poz-1;
}
}

int cdoi (int x)
{
	poz=cautare(x);
	if (poz!=-1)
		{do{poz--;} while (x==a[poz]);
		return poz+1;
		}
	else
	{
		poz=n;
		while (a[poz]>x) poz--;
		return poz+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) fout<<czero(x)<<'\n';
		if (c==1) fout<<cunu(x)<<'\n';
		if (c==2) fout<<cdoi(x)<<'\n';
	}
return 0;
}