#include <iostream>
#include <fstream>

#define NMAX 100002

using namespace std;

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

struct customSet
{
	int first = 0; // first appearance of a certain value 
 	int last = 0; // last appearance of a certain value
	int value = 0;
};

int n, m;
customSet set[NMAX];

int BinarySearch(int value , int maxValue)
{
	int left = 1, right = maxValue, middle;
	while (left <= right)
	{
		middle = (right + left) / 2;
		if (value == set[middle].value)
		{
			return middle;
		}
		if (value < set[middle].value)
		{
			right = middle - 1;
		}
		else if (value > set[middle].value)
		{
			left = middle + 1;
		}
	}
	return middle;
}

void Read(void)
{
	int i , prop, index = 1;
	fin >> n;
	for (i = 1; i <= n; i++)
	{
		fin >> prop;
		if (prop != set[index].value && set[index].value != 0)
		{
			set[index].last = i - 1;
			index++;
		}
		if (set[index].value == 0)
		{
			set[index].first = i;
			set[index].value = prop;
		}
	}
	set[index].last = n;
	fin >> m;
	int a , x;
	for (i = 1; i <= m; i++)
	{
		fin >> a >> x;
		prop = BinarySearch(x , index);
		switch (a)
		{
		case 0:
			if (set[prop].value != x)
			{
				fout << -1 << '\n';
			}
			else
			{
				fout << set[prop].last << '\n';
			}
			break;
		case 1:
			if (prop + 1 <= index && set[prop + 1].value <= x && set[prop].value > x)
			{
				prop = prop + 1;
			}
			else if (prop - 1 >= 1 && set[prop - 1].value <= x && set[prop].value > x)
			{
				prop = prop - 1;
			}
			fout << set[prop].last << '\n';
			break;
		case 2:
			if (prop + 1 <= index && set[prop + 1].value >= x && set[prop].value < x)
			{
				prop = prop + 1;
			}
			else if (prop - 1 >= 1 && set[prop - 1].value >= x && set[prop].value < x)
			{
				prop = prop - 1;
			}
			fout << set[prop].first << '\n';
			break;
		}
	}
}

int main(void)
{
	Read();
	return 0;
}