#include <stdio.h>
#define N_MAX 100010

int V[N_MAX];
int n, m;

void caut0(int x) {
	int st = 1, dr = n, m;
	while( st < dr ) {
		//printf("%d %d %d\n", st, dr, m);
		m = (st+dr)/2;
		if(V[m] <= x) st = m+1;
		else dr = m-1;
	}
	if(V[st] != x) st--;
	if(V[st] == x) {
		printf("%d\n", st);
	}
	else {
		printf("-1\n");
	}
}
void caut1(int x){
	int st = 1, dr = n, m;
	while( st <dr ) {
		m = (st+dr)/2;
		if(V[m] <= x) st = m+1;
		else dr = m-1;
	}
	if(V[st] != x && V[st-1] == x) st--;
	printf("%d\n", st);
}
void caut2(int x) {
	int st = 1, dr = n, m;
	while( st <dr ) {
		m = (st+dr)/2;
		if(V[m] < x) st = m+1;
		else dr = m-1;
	}
	if(V[st] != x && V[st+1] == x) st++;
	printf("%d\n", st);
}
	
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]);
	}
	scanf("%d", &m);
	for(int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		if(x == 0) caut0(y);
		else if(x == 1) caut1(y);
		else caut2(y);
	}
	return 0;
}