#include <stdio.h>
#define Nmax 110001

int N,M,x,y,m,r;
int v[Nmax];
void cauta0(int a,int b,int m)
{
	while(a<=b)
	{
		m=(a+b)/2;
		if (v[m]==x)
		{
			printf("%d\n",m);
			return ;
		}
		if(v[m]<x)
			a=m+1;
		else
			b=m-1;
	}	
	if(v[m]==x)
	{
		printf("%d\n",m);
		return;
	}	
	printf("-1\n");
}
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;
	}
	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;
	}
	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: {cauta0(1,N,x); break;}
			case 1: {cauta1(1,N,x); break;}
			case 2:	{cauta2(1,N,x); break;}
		}	
	}	
	return 0;
}