#include<fstream>		
using namespace std;
int v[100000],x,n,u,m;

int poz0(int x, int s, int d)
{
	if(d-s<=1)
		{
		if (v[d] == x)
			return d;
		else if(v[s]==x)
			return s;
		else
			return -1;
		}
	int mid=s+(d-s)/2;
	
	if(v[mid]>x)
		return	poz0(x,s,mid);
	else
		return poz0(x,mid,d);
}
	
int poz1(int x, int s, int d)
	{
	if(d-s<=1)
		{		
		if(v[d]<=x) 
			return d;
		else
			return s;
		}
		
	int mid=s+(d-s)/2;
	
	if(v[mid]>x) 
		return	poz1(x,s,mid);
	else 
		return poz1(x,mid,d);
	}
int poz2(int x, int s, int d)
{
	
	if(d-s<=1)
		{
		if(v[s]>=x)
			return s;
		else 
			return d; 
		}
	int mid=s+(d-s)/2;	
	
	if(v[mid]>=x)
		return	poz2(x,s,mid);
	else 
		return poz2(x,mid,d);

}

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

f>>n;

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

f>>m;

while(m--)
{
f>>u>>x;
switch(u)
{
case 0: g<<poz0(x,1,n)<<'\n'; break;
case 1: g<<poz1(x,1,n)<<'\n'; break;
case 2: g<<poz2(x,1,n)<<'\n'; break;
}
}

f.close();
g.close();

return 0;
}