#include <fstream>

using namespace std;

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

const int nmax=100002;
int n,k,v[nmax];

int binary_search0 (int left, int right, int x)
{
	int sol=-2;
	while (left <= right)
	{
		int mid=left+(right-left)/2;
		if (v[mid]==x)
		{
			sol=mid;
			left=mid+1;
		}
		else if (v[mid]<x)
		{
			left=mid+1;
		}
		else
			right=mid-1;
	}
	return sol+1;
}

int binary_search1 (int left, int right, int x)
{
	int sol=-2;
	while (left <= right)
	{
		int mid=left+(right-left)/2;
		if (v[mid]<=x)
		{
			sol=mid;
			left=mid+1;
		}
		else
			right=mid-1;
	}
	return sol+1;
}

int binary_search2 (int left, int right, int x)
{
	int sol=-2;
	while (left <= right)
	{
		int mid=left+(right-left)/2;
		if (v[mid]>=x)
		{
			sol=mid;
			right=mid-1;
		}
		else
			left=mid+1;
	}
	return sol+1;
}


int main ()
{
	fin>>n;
	for (int i=0; i<n; i++)
		fin>>v[i];
	fin>>k;
	for (int i=1, type, value; i<=k; i++)
	{
		fin>>type>>value;
		if (type==0)
			fout<<binary_search0 (0,n-1,value)<<"\n";
		else if (type==1)
			fout<<binary_search1 (0,n-1,value)<<"\n";
		else if (type==2)
			fout<<binary_search2 (0,n-1,value)<<"\n";
	}

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