#include <cstdio>
using namespace std;

FILE *f=fopen ("cautbin.in","r");
FILE *g=fopen ("cautbin.out","w");
int v[1000001];

int cauta1 (int x,int y, int z){
	int m;
	if(x>y){
		return -1;
	}
	if(x==y){
		if(v[x]==z){
			return x;
		}
		else{
			return -1;
		}
	}
	m=(x+y+1)/2;
	if (v[m]==z){
		return cauta1(m,y,z);
	}
	else{
		if (v[m]<z){
			return cauta1(m+1,y,z);
		}
		else{
			return cauta1(x,m-1,z);
		}
		
	}
}

int cauta2 (int x, int y, int z){
	int m;
	if(x>y){
		return -1;
	}
	if(x==y){
		return x;
	}
	m=(x+y+1)/2;
	
	if (v[m]<=z){
		return cauta2(m,y,z);
	}
	else{
		return cauta2(x,m-1,z);
	}
}

int cauta3 (int x, int y, int z){
	int m;
	if(x>y){
		return -1;
	}
	if(x==y){
		return x;
	}
	m=(x+y)/2;
	
	if (v[m]>=z){
		return cauta3(x,m,z);
	}
	else{
		return cauta3(m+1,y,z);
	}
}

int main(){
	int n,m,a,b,i,sol;
	
	fscanf (f,"%d",&n);
	for (i=1;i<=n;++i){
		fscanf (f,"%d",&v[i]);
	}
	fscanf (f,"%d",&m);
	
	for (i=1;i<=m;++i){
		fscanf (f,"%d%d",&a,&b);
		if (a==0){
			sol=cauta1(1,n,b);
		}
		else{
			if (a==1){
				sol=cauta2(1,n,b);
			}
			else{
				if (a==2){
					sol=cauta3(1,n,b);
				}
			}
		}
		fprintf (g,"%d\n",sol);
	}
	
	return 0;
}