#include <iostream.h>
#include <fstream.h>
#define NMAX 100000

int v[NMAX];
fstream f("cautbin.in");
fstream g("cautbin.out");

int c_b1(int x,int a,int b)
{
	int m;
	while(a<=b)
	{
		m=a+(b-a)/2;
		if(x<=v[m])
			b=m-1;
		else
			a=m+1;
	}
	
	while(v[m]==v[m+1])
		m++;
	
	if(v[m]==x)
		return m;
	else
		return -1;
}

int c_b2(int x,int a,int b)
{
	int m;
	while(a<=b)
	{
		m=a+(b-a)/2;
		if(x<=v[m])
			b=m-1;
		else
			a=m+1;
	}
	
	while(v[m]==v[m+1])
		m++;
	
	if(v[m]==x)
		return m;
	else
		return (m-1);
}

int c_b3(int x,int a,int b)
{
	int m;
	while(a<b)
	{
		m=(a+b)/2;
		if(v[m]<x)
			a=m+1;
		else
			b=m;
	}
	
	m=(a+b)/2;
	if(v[m]<x)
		m++;
	return m;
}

int main()
{
	int i,n,m,x,a,b,op;
	
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	
	if(x<v[n/2])
	{
		a=1;
		b=n/2;
	}
	else
	{
		a=n/2;
		b=n;
	}
	
	for(i=1;i<=m;i++)
	{
		f>>op;
		f>>x;
		switch(op)
		{
			case 0 :
				g<<c_b1(x,1,n)<<"\n";
			break;
			case 1 :
				g<<c_b2(x,1,n)<<"\n";
			break;
			case 2 :
				g<<c_b3(x,1,n)<<"\n";
			break;
		}
	}
	return 0;
}