#include<fstream>

using namespace std;

#define N 100005

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

int BS3(int* A, int n, int val)
{
	int left = 1;
	int  right = n;

	while(right - left > 1)
	{
		int middle = (left + right) / 2;
		if (A[middle] >= val)
		{
			right = middle;
		}
		else
		{
			left = middle + 1;
		}
	}

	if (A[left] >= val) return left;
	if (A[right] >= val) return right;
}
int BS2(int* A, int n, int val)
{
	int left = 1;
	int right = n;

	while (right - left > 1)
	{
		int middle = (left + right) / 2;
		if (A[middle] <= val)
		{
			left = middle;
		}
		else
		{
			right = middle - 1;
		}
	}

	if (A[right] <= val) return right;
	if (A[left] <= val) return left;
}
int BS1(int* A, int n, int val)
{
	int left = 1;
	int right = n;

	while (right - left > 1)
	{
		int middle = (left + right) / 2;
        if (A[middle] <= val)
		{
			left = middle;
		}
		else
		{
			right = middle - 1;
		}
	}

	if (A[right] == val) return right;
	if (A[left] == val) return left;
	return -1;
}


int main()
{
	int m, n, A[N];

	f >> n;
	for(int i = 1; i <= n; i++)
	{
		f >> A[i];
	}

	f >> m;
	for(int i = 1; i <= m; i++)
	{
		int codop, val;
		f >> codop >> val;

		if (codop == 0)
		{
			g << BS1(A, n, val) << "\n";
		}

		if (codop == 1)
		{
			g << BS2(A, n, val) << "\n";
		}

		if (codop == 2)
		{
			g << BS3(A, n, val) << "\n";
		}
	}
}