#include<fstream.h>

int n,m,x[100001],a,b;

int caut0(int st,int dr)
{
	int m;
	while(st<dr)
	{
		m=st+(dr-st)/2;
		if(b>=x[m])st=m+1;
		else dr=m-1; 
	}
	m=st+(dr-st)/2;
	if(b==x[m]) return m;
	if(b==x[m-1]) return m-1;
	return -1;
}

int caut1(int st,int dr)
{
	int m;
	while(st<dr)
	{
		m=st+(dr-st)/2;
		if(b>x[m])st=m+1;
		else dr=m-1; 
	}
	m=st+(dr-st)/2;
	if(b>=x[m]) return m;
	return m-1;
}

int caut2(int st,int dr)
{
	int m;
	while(st<dr)
	{
		m=st+(dr-st)/2;
		if(b>x[m])st=m+1;
		else dr=m-1; 
	}
	m=st+(dr-st)/2;
	if(b<=x[m]) return m;
	return m+1;
}

int main()
{
	int i;
	ifstream f("cautbin.in");ofstream g("cautbin.out");
	f>>n;for(i=1;i<=n;i++)f>>x[i];
	f>>m;
	for(i=1;i<=m;i++)
	{
		f>>a>>b;
		if(a==0)g<<caut0(1,n)<<'\n';
		else if(a==1)g<<caut1(1,n)<<'\n';
			 else g<<caut2(1,n)<<'\n';
	}
	f.close();g.close();
	return 0;
}