#include <fstream>
using namespace std;

long long n,a[100001],m,x,y;

int bin_search0(int st, int dr, int x)
{
	int mij,ok = 0;
	while(st < dr && !ok)
	{
		mij = (st + dr) / 2;
		if(a[mij] == x) ok = 1;
		if(a[mij] > x) dr = mij - 1;
		if(a[mij] < x) st = mij + 1;		
	}
	if(ok)
	{
		while(a[mij] == x)
			++mij;
		return mij - 1;
	}
	else return -1;
	
}

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

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

int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(int i = 1; i <= n; ++i)
		f>>a[i];
	f>>m;
	for(int i = 1; i <= m; ++i)
	{
		f>>y>>x;
		switch(y)
		{
			case 0: g<<bin_search0(1, n, x)<<'\n'; break;
			case 1: g<<bin_search1(1, n, x)<<'\n'; break;
			case 2: g<<bin_search2(1, n, x)<<'\n'; break;
		}
	}
	f.close();
	g.close();
	return 0;
}