#include<stdio.h>

int n,m,i,v[100200],cod,x;

int caut0(int x)
{
	int i=1,j=n,m,indice;
	indice=-1;
	while (i<=j) {
		m=(i+j)/2;
		if (v[m]<=x) i=m+1;
		else j=m-1;
		if (v[m]==x) indice=m;
	}
	return indice;
}

int caut1(int x)
{
	int i=1,j=n,m,indice;
	while(i<=j) {
		m=(i+j)/2;
		if (v[m]<=x){
			i=m+1;
			indice=m;
		}
		else j=m-1;
	}
return indice;
}


int caut2(int x)
{
	int i=1,j=n,m,indice;
	while (i<=j) {
		m=(i+j)/2;
		if (v[m]>=x) {
			j=m-1;
			indice=m;
		}
		else i=m+1;
	}
	return indice;
}


int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d", &n);
	for (i=1;i<=n;i++) scanf("%d", &v[i]);
	
	scanf("%d",&m);
	for (i=1;i<=m;i++) {
		scanf("%d %d",&cod,&x);
		if (cod==0) printf("%d\n", caut0(x));
		else if (cod==1) printf("%d\n", caut1(x));
		else if (cod==2) printf("%d\n",caut2(x));
	}
	return 0;
}