#include <fstream>
#define DIM 100005

using namespace std;

int n,m,x,v[DIM],b;
ifstream f("cautbin.in");
ofstream g("cautbin.out");


long caut0(long lo, long hi) 
{
	long mij;
	mij=lo+(hi-lo)/2;
	if(lo<=hi)
	{
		if(v[mij]==x and v[mij+1]!=x) b=mij;
		else caut0(mij+1,hi);
		if(v[mij]<x) caut0(mij+1,hi);
		else caut0(lo,mij-1);
	}
	return b;
}


long caut1(long lo, long hi) 
{
	long mij;
	mij=lo+(hi-lo)/2;
	if(lo<=hi)
	{
		if(v[mij]<=x)
			{b=mij;caut1(mij+1,hi);}
		else
			caut1(lo,mij-1);
	}
	return b;
}




long caut2(long lo, long hi) 
{
	long mij;
	mij=lo+(hi-lo)/2;
	if(lo<=hi)
	{
		if(v[mij]>=x)
			{b=mij;caut2(lo,mij-1);}
		else
			caut2(mij+1,hi);
	}
	return b;
}



int main()
{
	int i,a;
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	for(i=1;i<=m;i++)
	{
		f>>a>>x;b=-1;
		if(a==0) g<<caut0(1,n)<<"\n";
		if(a==1) g<<caut1(1,n)<<"\n";
		if(a==2) g<<caut2(1,n)<<"\n";
	}
	f.close();
	g.close();
	return 0;
}