#include <fstream>

using namespace std;

int n, i, m, mode, mid, tmp;
long int x;
long int sir[100000];

int bin_search_0(int beg, int end);
int bin_search_1(int beg, int end);
int bin_search_2(int beg, int end);

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

	fin >> n;

	for (i=0; i<n; i++)
	{
		fin >> sir[i];
	}

	fin >> m;
	
	for (i=0; i<m; i++)
	{
		fin >> mode;
		fin >> x;
		switch (mode)
		{
		case 0:
			fout << bin_search_0(0, n-1) << "\n";
			break;
		case 1:
			fout << bin_search_1(0, n-1) << "\n";
			break;
		case 2:
			fout << bin_search_2(0, n-1) << "\n";
			break;
		}
	}

	fin.close();
	fout.close();

	return 0;
}

int bin_search_0(int beg, int end)
{
	tmp=-2;
	while (beg<=end)
	{
		mid=beg+(end-beg)/2;
		if (sir[mid]>x)
		{
			end=mid-1;
		}
		else if (sir[mid]<x)
		{
			beg=mid+1;
		}
		else
		{
			tmp=mid;
			beg=mid+1;
		}
	}
	return tmp+1;
}

int bin_search_1(int beg, int end)
{
	tmp=-2;
	while (beg<=end)
	{
		mid=beg+(end-beg)/2;
		if (sir[mid]>x)
		{
			end=mid-1;
		}
		else
		{
			tmp=mid;
			beg=mid+1;
		}
	}
	return tmp+1;
}

int bin_search_2(int beg, int end)
{
	while (beg<=end)
	{
		mid=beg+(end-beg)/2;
		if (sir[mid]<x)
		{
			beg=mid+1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}