#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
long a[1000005],n;
void cautbin(long x, long y, long st, long dr)
{
	int ok=0;
	long m;
	while (!ok && st<=dr)
	{
		m=(st+dr)/2;
		if (a[m]==y)
			if (x<=1) 
			{
				while (m<=n-1 && a[m]==y) m++;
				fout<<m<<endl;
				ok=1;
			}
			else
			{
				while (m-1 && a[m]==y) m--;
				fout<<m+1<<endl;
				ok=1;
			}
		else
			if (a[m]<y) 
				st=m+1;
			else dr=m-1;
	}
	if (!ok)
		switch(x)
		{
		case 0: fout<<"-1"<<endl;
				break;
		case 1: fout<<dr<<endl;
				break;
		case 2: fout<<st<<endl;
				break;
		}
}
int main()
{
	long i,m,x,y;
	fin>>n;
	for (i=0;i<n;i++)
		fin>>a[i];
	fin>>m;
	for (i=0;i<m;i++)
	{
		fin>>x>>y;
		cautbin(x,y,0,n-1);
	}
	return 0;
}