#include <cstdio>

int v[100005];

int cautbin0(int x, int n){
	int mid, lo=1, hi=n;

	mid=lo+(hi-lo)/2;
	while(hi>lo && v[mid]!=x){
		mid=lo+(hi-lo)/2;
		if(x>v[mid])
			lo=mid+1;
		else
			hi=mid-1;
	}
	
	if(v[mid]==x){
		for(; v[mid]==x; ++mid);
		return mid-1;
	}
	return -1;
}

int cautbin1(int x, int n){
	int mid, lo=1, hi=n;

	mid=lo+(hi-lo)/2;
	while(hi>lo && v[mid]!=x){
		mid=lo+(hi-lo)/2;
		if(x>v[mid])
			lo=mid+1;
		else
			hi=mid-1;
	}
	
	if(v[mid]==x){
		for(; v[mid]==x; ++mid);
		return mid-1;
	}
	else{
		for(; v[mid]>x; --mid);
		return mid;
	}
}

int cautbin2(int x, int n){
	int mid, lo=1, hi=n;

	mid=lo+(hi-lo)/2;
	while(hi>lo && v[mid]!=x){
		mid=lo+(hi-lo)/2;
		if(x>v[mid])
			lo=mid+1;
		else
			hi=mid-1;
	}
	
	if(v[mid]==x){
		for(; v[mid]==x; --mid);
		return mid+1;
	}
	else{
		for(; v[mid]<x; ++mid);
		return mid;
	}
}

int main(){
	
	
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	int n, m, i, j, aux, x;
	
	scanf("%d",&n);
	
	for(i=1; i<=n; ++i){
		scanf("%d",&v[i]);
	}
	
	scanf("%d",&m);
	
	for(; m--; ){
		scanf("%d",&aux);
		scanf("%d",&x);
		if(aux==0)
			printf("%d\n",cautbin0(x, n));
		if(aux==1)
			printf("%d\n",cautbin1(x,n));
		if(aux==2)
			printf("%d\n",cautbin2(x,n));
	}
}