#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 i=b;
	while(x!=v[i]&&a<=i)
		i--;
	if(i) return i;
	else return -1;
}

int c_b2(int x,int a,int b)
{
	int i=b;
	while((x<v[i]||x!=v[i])&&a<=i)
		i--;
	return i;
}

int c_b3(int x,int a,int b)
{
	int i=a;
	while((x<v[i]||x!=v[i])&&i<=b)
		i++;
	return i;
}

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,a,b)<<"\n";
			break;
			case 1 :
				g<<c_b2(x,a,b)<<"\n";
			break;
			case 2 :
				g<<c_b3(x,a,b)<<"\n";
			break;
		}
	}
	return 0;
}