#include <stdio.h>
#define Nmax 100001

int N,M,x,y,m,r;
short int v[Nmax];
int cauta0(int a,int b,int m)
{
	while(a<b)
	{
		m=(a+b)/2;
		if(v[m]<x)
			a=m+1;
		else
			b=m-1;
		if(v[m]==x)
		{
		while(v[m]==x)
			++m;
		printf("%d\n",m-1);
		return 1;
		}	
	}	
	m=(a+b)/2;
	if(v[m]==x)
	{
		while(v[m]==x)
			++m;
		printf("%d\n",m-1);
		return 1;
	}	
	return 0;
}
void cauta1(int a,int b,int x)
{
	while(a<b)
	{
		m=(a+b)/2;
		if (v[m]<x)
			a=m+1;
		else
			b=m-1;
		if(v[m]==x)
		{
		while(v[m]==x)
			++m;
		printf("%d\n",m-1);
		return;
		}	
	}
	m=(a+b)/2;
	if (v[m]>x) 
		--m;
	printf("%d\n", m);
}
void cauta2(int a,int b,int m)
{
	while(a<b)
	{
		m=(a+b)/2;
		if (v[m]<x)
			a=m+1;
		else
			b=m-1;
		if(v[m]==x)
		{
		while(v[m]==x)
			++m;
		printf("%d\n",m-1);
		return;
		}	
	}
	m=(a+b)/2;
	if (v[m]<x) 
		++m;
	printf("%d\n", m);
}
int main()
{
	freopen("cautbin.in", "r",stdin);
	freopen("cautbin.out", "w",stdout);
	scanf("%d", &N);
	for(int i=1;i<=N;++i)
		scanf("%d",&v[i]);
	scanf("%d", &M);
	for(int i=1;i<=M;++i)
	{
		scanf("%d%d", &y,&x);
		switch(y)
		{
			case 0: { if(!cauta0(0,N,x)) printf("-1\n"); break;}
			case 1: { cauta1(1,N,x); break;}
			case 2: { cauta2(1,N,x); break;}
		}	
	}	
	return 0;
}