# include <fstream>
using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

int n,v[100000];

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

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

int caut2(int x)
{
	int st,dr,mij;
	st=1;
	dr=n;
	while(st<dr)
	{
		mij=(st+dr)/2;
		if(x<=v[mij])
			dr=mij;
		else
			st=mij+1;
	}
	return st;
}

int main()
{
	int M,x,p,i;
	in>>n;
	for(i=1;i<=n;++i)
		in>>v[i];
	in>>M;
	while(M--)
	{
		in>>p>>x;
		if(p==0)
		{
			out<<caut0(x)<<"\n";
			continue;
		}
		if(p==1)
		{
			out<<caut1(x)<<"\n";
			continue;
		}
		if(p==2)
		{
			out<<caut2(x)<<"\n";
			continue;
		}
	}
	return 0;
}