using namespace std;

#include<fstream>
#include<iostream>

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n,m;
int v[100001];

int searchedValue,type;

int binarySearch(int left,int right)
{
	if(left == right && type!=0)
		return left;
	else
		if(left==right && type ==0)
		{
			if(v[left] == searchedValue)
				return left;
			else
				return -2;
		}

		int middle = (left + right)/2;

		if(type==0)
		{
			if(v[middle+1]> searchedValue)
				return binarySearch(left,middle);
			else
				return binarySearch(middle+1,right);
		}
		else
		if(type==1)
		{
			if(v[middle+1] > searchedValue)
				return binarySearch(left,middle);
			else
				return binarySearch(middle+1,right);
		}
		else
		if(type==2)
		{
			if(v[middle] < searchedValue)
				return binarySearch(middle+1,right);
			else
				return binarySearch(left,middle);
		}

}

int main()
{
	f>>n;

	for(int i=0;i<n;i++)
		f>>v[i];

	f>>m;

	for(int i=0;i<m;i++)
	{
		f>>type>>searchedValue;

		g<<binarySearch(0,n-1)+1<<'\n';
	}
	//system("pause");
	return 0;
}