#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);
		if (y==0)
			cauta0(1,N,x);
		if (y==1)
			cauta1(1,N,x);
		if (y==2)
			cauta2(1,N,x);
	}	
	return 0;
}