#include<fstream>
using namespace std;
int n,m,i,st,dr,x,y,v[100001],mo;
int main()
{
	int ok;
	ifstream in("cautbin.in");
	ofstream out("cautbin.out");
	in>>n;
	for(i=1;i<=n;i++)
		in>>v[i];
	in>>mo; 
	for(i=1;i<=mo;i++)
	{	
	in>>x>>y;
	if(x==0)
	{
		st=1;
		dr=n;
		while (st!=dr)
			{
			m=(st+dr+1)/2;
			if(y>=v[m])
			st=m;
			else
			dr=m-1;
			}
		if(y!=v[st])
		ok=-1;
		else
		ok=st;
	}
	if(x==1)
	{	
		st=1;
		dr=n;
		while (st!=dr)
			{
			m=(st+dr)/2;
			if(y<v[m])
			dr=m;
			else
			st=m+1;
			}
		if(v[st]>y)
			ok=st-1;
		else
			ok=st;
	}
	if(x==2)
	{	
		st=1;
		dr=n;
		while (st!=dr)
		{
		m=(st+dr)/2;
		if(y<=v[m])
		dr=m;
		else
		st=m+1;
		}
		if(v[st]<y)
			ok=st+1;
		else
			ok=st;
	}
	out<<ok<<endl;
	}
	in.close();
	out.close();
	return 0;
}