#include<iostream>
#include<fstream>
int cautareBinara1(int *vector, int stanga, int dreapta, int val, int dim)
{
	if (stanga > dreapta)
	{
		return -1;
	}
	else
	{
		int m = (stanga + dreapta) / 2;
		if (vector[m] == val)
		{
			if (m == dim - 1)
			{
				return m + 1;
			}
			else
			{
				if (vector[m + 1] != val)
				{
					return m + 1;
				}
				else
				{
					return cautareBinara1(vector, m + 1, dreapta, val, dim);
				}
			}
		}
		else
		{
			if (val > vector[m])
			{
				return cautareBinara1(vector, m + 1, dreapta, val, dim);
			}
			else
			{
				return cautareBinara1(vector, stanga, m - 1, val, dim);
			}
		}

	}

}
int cautareBinara2(int *vector, int stanga, int dreapta, int val, int dim)
{
	if (stanga > dreapta)
	{
		return -1;
	}
	else
	{
		int m = (stanga + dreapta) / 2;
		if (vector[m] <= val)
		{
			if (m == dim - 1)
			{
				return m + 1;
			}
			else
			{
				if (vector[m + 1]>val)
				{
					return m + 1;
				}
				else
				{
					return cautareBinara2(vector, m + 1, dreapta, val, dim);
				}
			}
		}
		else
		{

			return cautareBinara2(vector, stanga, m - 1, val, dim);

		}

	}

}
int cautareBinara3(int *vector, int stanga, int dreapta, int val, int dim)
{
	if (stanga > dreapta)
	{
		return -1;
	}
	else
	{
		int m = (stanga + dreapta) / 2;
		if (vector[m] >= val)
		{
			if (m == 0)
			{
				return m + 1;
			}
			else
			{
				if (vector[m - 1]<val)
				{
					return m + 1;
				}
				else
				{
					return cautareBinara3(vector, stanga, m - 1, val, dim);
				}
			}
		}
		else
		{

			return cautareBinara3(vector, m + 1, dreapta, val, dim);

		}

	}

}


int main()
{
	int n, *vector, m, mutare, x;
	std::ifstream f("cautbin.in");
	std::ofstream g("cautbin.out");
	f >> n;
	vector = (int*)malloc(n * sizeof(int));
	for (int index = 0; index <n; ++index)
	{
		f >> vector[index];
	}
	f >> m;
	for (int index = 0; index < m; ++index)
	{
		f >> mutare >> x;
		if (mutare == 0)
		{
			g << cautareBinara1(vector, 0, n - 1, x, n);
		}
		else
		{
			if (mutare == 1)
			{
				g << cautareBinara2(vector, 0, n - 1, x, n);
			}
			else
			{
				g << cautareBinara3(vector, 0, n - 1, x, n);
			}
		}
		g << std::endl;
	}
	f.close();
	g.close();


	system("pause");
}