#define MAX_N 100000

#include <fstream>
using namespace std;

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

int n, m, a[MAX_N + 1];

int LS(int x);
int LJ(int x);
int Cb(int x);

int main()
{
	fin >> n;
	for (int i = 1; i <= n; ++i)
	{
		fin >> a[i];
	}
	
	fin >> m;
	for (int i = 0, x, y; i < m; ++i)
	{
		fin >> x >> y;
		
		if (x == 0)
		{
			fout << Cb(y) << '\n';
		}
		if (x == 1)
		{
			fout << LS(y) << '\n';	
		}
		if (x == 2)
		{
			fout << LJ(y) << '\n';
		}
	}
	
	fin.close();
	fout.close();
	return 0;
}


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

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

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