#include <fstream>

#define N 100001

using namespace std;

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

int i,n,m,c,x,v[N];

int binSearch ( int x )
{
	int st, mij, dr;

	st = 1, dr = n;
	while ( st < dr )
	{
		mij = (st + dr) / 2;

		if ( x > v[mij] )
			st = mij + 1;
		else if ( x < v[mij] )
			dr = mij - 1;
		else
		{
			int x = v[mij];

			while ( v[mij] == x )
				++mij;

			return mij - 1;
		}
	}

	return -1;
}

int upperBound ( int x )
{
	int st, mij, dr;

	st = 1, dr = n;
	while ( st <= dr )
	{
		mij = (st + dr) / 2;

		if ( x > v[mij] )
			st = mij + 1;
		else
			dr = mij - 1;
	}

	return st;
}

int lowerBound ( int x )
{
	int st, mij, dr;

	st = 1, dr = n;
	while ( st <= dr )
	{
		mij = (st + dr) / 2;

		if ( x < v[mij] )
			dr = mij - 1;
		else
			st = mij + 1;
	}

	return dr;
}

int main()
{
	fin >> n;

	for ( i = 1; i <= n; ++i )
		fin >> v[i];

	fin >> m;

	for ( i = 0; i < m; ++i )
	{
		fin >> c >> x;

		switch (c)
		{
			case 0 :
				fout << binSearch (x) << '\n';
				break;
			case 1 :
				fout << lowerBound (x) << '\n';
				break;
			case 2 :
				fout << upperBound (x) << '\n';
				break;
		}
	}
}