#include <fstream>
using namespace std;

int v[1<<17],n;

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

int bs0(int x)
{
	int i,step=1<<16;
	for (i=0;step;step>>=1)
		if (i+step<=n && v[i+step]<=x)
			i+=step;
	if (v[i]==x)
		return i;
	return -1;
}

int bs1(int x)
{
	int i,step=1<<16;
	for (i=0;step;step>>=1)
		if(i+step<=n && v[i+step]<=x)
			i+=step;
	return i;
}

int bs2(int x)
{
	int i,step=1<<16;
	for (i=0;step;step>>=1)
		if (i+step<=n && v[i+step]<x)
			i+=step;
	return i+1;
}

int work(int a,int x)
{
	if (!a)
		return bs0(x);
	if (a==1)
		return bs1(x);
	return bs2(x);
}

int main()
{
	int i,m,a,x;
	in>>n;
	for (i=1;i<=n;i++)
		in>>v[i];
	in>>m;
	while (m--)
	{
		in>>a>>x;
		out<<work(a,x)<<"\n";
	}
	return 0;
}