#include <stdio.h>
#define Nmax 100001

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