//		http://infoarena.ro/problema/cautbin
#include <fstream>
#define DIM 100000
using namespace std;

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

int n,b=-1;

int v[DIM];

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

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


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