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

/**
 *	Returns the the largest index i, such that array[i] == value or -1 if 'value' is not in the array.
 */
int findBinary1(int * array, int low, int high, int value)
{
	if(low > high)
		return -1;
	
	int middle = (low + high) / 2;
	
	if(array[middle] == value)
	{
		if(middle < high)
		{
			if(array[middle + 1] == value)
			{
				return findBinary1(array, middle + 1, high, value);
			}
			else
			{
				return middle;
			}
		}
	}
	else if(array[middle] < value) 
	{
		return findBinary1(array, middle + 1, high, value);
	} 
	else 
	{
		return findBinary1(array, low, middle - 1, value);
	}
}

/**
 *	Returns the largest index i, such that array[i] <= value. Such an index i will always exist.
 */
int findBinary2(int * array, int low, int high, int value)
{
	if(low > high)
		return -1;
	
	int middle = (low + high) / 2;
	
	if(array[middle] <= value)
	{
		if(middle < high)
		{
			if(array[middle + 1] > value)
				return middle;
			else
				return findBinary2(array, middle + 1, high, value);
		}
		else
		{
			return middle;
		}
	}
	else
	{
		return findBinary2(array, low, middle - 1, value);
	}
}

/**
 *	Returns the smallest index i, such that array[i] >= value. Such an index i will always exist.
 */
int findBinary3(int * array, int low, int high, int value)
{
	if(low > high)
		return -1;
	
	int middle = (low + high) / 2;
	
	if(array[middle] >= value)
	{
		if(middle > low)
		{
			if(array[middle - 1] < value)
			{
				return middle;
			}
			else
			{
				return findBinary3(array, low, middle - 1, value);
			}
		}
		else
		{
			return middle;
		}
	}
	else
	{
		return findBinary3(array, middle + 1, high, value);
	}
}

/**
 *	Function pointer typedef for the type of these 3 functions.
 */
typedef int (*BinarySearchFuncPtr)(int *, int, int, int);

int main()
{	
	const char * inFile = "cautbin.in";
	const char * outFile = "cautbin.out";
	
	ifstream fin(inFile);
	ofstream fout(outFile);
	
	/**
	 *	For convenience...
	 */
	BinarySearchFuncPtr opFunc[3];
	opFunc[0] = findBinary1;
	opFunc[1] = findBinary2;
	opFunc[2] = findBinary3;
	
	/**
	 *	Read in the array.
	 */
	int length;
	fin	>> length;
	
	int array[length];
	for(int i = 0; i < length; i++)
	{
		fin >> array[i];
	}
	
	/**
	 *	Read in the operations and execute each one.
	 */
	int numOps;
	fin >> numOps;
	
	while(numOps--)
	{
		int op, value;
		
		fin >> op >> value;
		
		cout << opFunc[op](array, 0, length -1, value) + 1 << "\n";
	}

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