#include<iostream>;
#include<fstream>
using namespace std;


int main()
{
	
	int n, m, left, right, var, array[100001], caz, number, mid;
	ofstream cautbin;
	cautbin.open("cautbin.out");
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> var;
		array[i] = var;
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		left = array[1];
		right = array[n];
		cin >> caz >> number;

		if (caz == 0)
		{
			bool go = true;
			while (go == true)
			{
				mid = left + (right - left) / 2;
				if (mid == left)
				{
					int answer = -1;
					if (array[left] == number)
						answer = left;
					if (array[right] == number)
						answer = right;
					cautbin << answer <<endl;
					go = false;
				}
				if (number >= array[mid])
				{
					left = mid;
				}
				else
				{
					right = mid;
				}
			}
		}

		if (caz == 1)
		{
			bool go = true;
			while (go == true)
			{
				mid = left + (right - left) / 2;
				if (mid == left)
				{
					int answer = left;
					if (array[right] <= number)
						answer = right;
					cautbin << answer << endl;
					go = false;
				}
				if (number >= array[mid])
				{
					left = mid;
				}
				else
				{
					right = mid;
				}
			}
		}

		if (caz == 2)
		{
			bool go = true;
			while (go == true)
			{
				mid = left + (right - left) / 2;
				if (mid == left)
				{
					int answer = right;
					if (array[left] >= number)
						answer = left;
					cautbin << answer << endl;
					go = false;
				}
				if (number > array[mid])
				{
					left = mid;
				}
				else
				{
					right = mid;
				}
			}
		}
	
	
	}
	

    return 0;
}