#include<fstream>
#define dmax 100004
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

int n,m,a;
long int x[dmax],b;

void bins()
{	int l,r,m;

	l=1 , r=n;
	
	while(l<=r && x[m]!=b)		
	{	m=(l+r)/2;	
		
		if(x[m] < b)
			l=m+1;
		
		if(x[m] > b)
			r=m-1;
	}

	if(a==0)
	{	while(x[m+1]==b)
			m++;
		if(x[m] != b)
			m=-1;
	}	
	if(a==1)
	{	
		m--;
		while(x[m+1] <= b && m<n)
			m++;
	}
	if(a==2)
	{	
		m++;
		while(x[m-1] >= b && m>0)	
			m--;
	}	
	out<<m<<'\n';
}	
	

int main()
{	int i;
	in>>n;
	for(i=1;i<=n;i++)
		in>>x[i];
	in>>m;
	for(i=1;i<=m;i++)
	{	in>>a>>b;
		bins();
	}
	in.close();
	out.close();
	return 0;
}