#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;
	while(lo<=hi)
	{
		mij=lo+(hi-lo)/2;
		if(v[mij]<x) lo=mij+1;
		else if(v[mij]>x) hi=mij-1;
		else if(v[mij]==x and v[mij+1]!=x) return mij;
		else lo=mij+1;
	}
	return b;
}

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

long caut2(long lo,long hi)
{
	long mij;
	while(lo<=hi)
	{
		mij=lo+(hi-lo)/2;
		if(v[mij]>=x) {b=mij;hi=mij-1;}
		else lo=mij+1;
	}
	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;
}