#include <fstream>
#define NM 100005

using namespace std;

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

int n, V[NM], m;

int CautBin(long long a, long long b)
{
	long long st = 1, dr = n, i;
	if (b == 24)
		int x = 0;
	while (st < dr)
	{
		long long mijl = st+ (dr-st) / 2;
		if (V[mijl] == b)
		{
			if (a == 0 || a == 1)
			{
				for (i = mijl + 1; i <= n; i++)
				{
					if (V[i] != b)
						return i - 1;
				}
				return n;
			}
			else
			{
				for (i = mijl - 1; i >= 1; i--)
				{
					if (V[i] != b)
						return i + 1;
				}
				return 1;
			}
		}
		if (V[mijl] < b)
		{
			st = mijl + 1;
		}
		if (V[mijl] > b)
		{
			dr = mijl - 1;
		}
	}
	if (a == 0)
	{
		if (V[st] == b)
			return st;
		else
			return -1;
	}
	if (a == 1)
	{
		if (V[st] > b)
			return st - 1;
		else
			return st;
	}
	if (a == 2)
	{
		if (V[st] >= b)
			return st;
		else
			return st+1;
	}
}

int main()
{
	long long i, a, b;
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> V[i];
	fin >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> a >> b;
		fout << CautBin(a, b) << '\n';
	}
	return 0;
}