#include<cstdio>
#include<fstream>
using namespace std;

int M,N,v[1000000],c,x;

int bin0(int x,int st,int dr)
{
	if(st=dr&&v[st]!=x)return -1;
	else 
		if(v[dr]==x)return dr;
		else 
			if(v[dr/2]<x)return bin0(x,st,dr/2);
			else return bin0(x,dr/2,dr);
}
int bin1(int x,int st,int dr)
{
	if(st=dr)return st;
		else 
		if(v[dr/2]<x)return bin0(x,st,dr/2);
		else return bin0(x,dr/2,dr);
}
int bin2(int x,int st,int dr)
{
	if(st=dr)return st;
		else 
		if(v[dr/2]<x)return bin0(x,st,dr/2);
		else return bin0(x,dr/2,dr);
}
int main()
{

	freopen("cautbin.in","r",stdin);
	ofstream out("cautbin.out");
	scanf("%d",&M);
	for(int i=1;i<M;++i)
		scanf("%d",&v[i]);
	scanf("%d",&N);
	for(int j=1;j<N;++j)
	{
		scanf("%d %d",&c,&x);
		if(c==0)bin0(x,1,M);
		else if(c==1)bin1(x,1,M);
		else bin2(x,1,M);
	}
	
	
	return 0;
}