#include <stdio.h>
#define N 100001
#define INF 2000000000
int v[N];
int n;
int cautbin0(int x) {
	int st = 1, dr = n, m;
	while(dr - st >= 2) {
		m = (st+dr)/2;
		//printf("***%d %d -> %d\n", st, dr,m);
		if(v[m] <= x) st = m;
		else dr = m;
	}
	if(v[dr] == x) return dr;
	if(v[st] == x) return st;
	return -1;
}
int cautbin1(int x) {
	int st = 1, dr = n, m;
	while(dr - st >= 2) {
		m = (st+dr)/2;
		if(v[m] <= x) st = m;
		else dr = m;
	}
	if(v[dr] <= x) return dr;
	return st;
	
}
int cautbin2(int x) {
	int st = 1, dr = n, m;
	while(dr - st >= 2) {
		m = (st+dr)/2;
		if(v[m] < x) st = m;
		else dr = m;
	}
	if(v[st] >= x) return st;
	return dr;
}
int main(){
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d", &n);
	for(int i = 1;i <= n; i++) {
		scanf("%d",&v[i]);
	}
	v[n+1] = INF;
	int m;
	scanf("%d", &m);
	for(int i =1 ;i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		if(x == 0) printf("%d\n", cautbin0(y));
		else if(x == 1) printf("%d\n", cautbin1(y));
		else printf("%d\n", cautbin2(y));
	}
	return 0;
}