#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/=2;
		if(a>=b && v[m]!=x)
			break;
		if(v[m]>x)
			{b=m-1; m=a+m-1;}
		else
			if(v[m]<x)
				{a=m+1; m=m+1+b;}
		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;
	}
	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;
	}
	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);
		m=1+N;
		switch(y)
		{
			case 0: { if(!cauta0(1,N,x)) printf("-1\n"); break;}
			case 1: { cauta1(1,N,x); break;}
			case 2: { cauta2(1,N,x); break;}
		}	
	}	
	return 0;
}