#include <cstdio>
#define NMax 100021

int a[NMax],n,m,type,x;

int caut_bin0(int lo,int hi,int val) {
	hi++;lo--;
	int mid;
	while(hi-lo > 1) {
		mid=lo+(hi-lo)/2;
		if(val<a[mid])
			hi=mid;
		else
			lo=mid;
	}
	if(a[lo]==val)
		return lo;
	return -1;
}

int caut_bin1(int lo,int hi,int val) {
	hi++;lo--;
	int mid;
	while(hi-lo > 1) {
		mid=lo+(hi-lo)/2;
		if(val<a[mid])
			hi=mid;
		else
			lo=mid;
	}
	return lo;
}

int caut_bin2(int lo,int hi,int val) {
	hi++;lo--;
	int mid;
	while(hi-lo > 1) {
		mid=lo+(hi-lo)/2;
		if(val<=a[mid])
			hi=mid;
		else
			lo=mid;
	}
	return hi;
}

int main() {
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);

	scanf("%d",&n);
	for(int o=1;o<=n;o++)
		scanf("%d",&a[o]);


	scanf("%d",&m);
	for(int o=1;o<=m;o++) {
		scanf("%d %d",&type,&x);
		switch(type) {
		case 0: printf("%d\n",caut_bin0(1,n,x)); 
			break;
		case 1: printf("%d\n",caut_bin1(1,n,x));
			break;
		case 2: printf("%d\n",caut_bin2(1,n,x));
		}
	}
	return 0;
}