#include<fstream>

using namespace std;

ifstream f ("cautbin.in");
ofstream g("cautbin.out");
int n,i,t,x,v[100005],m;

int cautbinar0(int st, int dr, int x)
{
	int m;
	while (st<=dr)
	{
		m=(st+dr)/2;
		if (v[m]<=x)	st=m+1;
		else dr=m-1;
	}
	m=(st+dr)/2;
	if (v[m]>x) m--;
	if (v[m]==x) return m;
	return -1;
}

int cautbinar1(int st, int dr, int x)
{
	int m;
	while (st<dr)
	{
        m=(st+dr)/2;
        if (v[m]<=x)	st=m+1;
        else	dr=m;
    }
	m=(st+dr)/2;
	if (v[m]>x)	m--;
	return m;
}

int cautbinar2(int st, int dr, int x)
{
	int m;
	while (st<dr)
	{
        m=(st+dr)/2;
        if (v[m]<=x)	st=m+1;
        else	dr=m;
    }
	m=(st+dr)/2;
	if (v[m]<x)	m++;
	return m;
}

int main ()
{
	f>>n;
	for (i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	for (i=1;i<=m;i++)
	{
		f>>t>>x;
		if (t==0)	g<<cautbinar0(1,n,x)<<"\n";
		if (t==1)	g<<cautbinar1(1,n,x)<<"\n";
		if (t==2)	g<<cautbinar2(1,n,x)<<"\n";
	}
	f.close();
	g.close();
	return 0;
}