#include<cstdio>
FILE *fin = freopen("cautbin.in", "r", stdin), 
		 *fout = freopen("cautbin.out", "w", stdout);

using namespace std;
int n, m;
int v[100001];

int CautareBinara(int st, int dr, int comanda, int x) {
	if(st > dr)
		if(comanda == 1 || v[dr] == x) return dr;
		else if(comanda == 2) return st; 
		else return -1;
		
	int m = (st + dr) / 2;		
	if(v[m] < x || (comanda < 2 && v[m] == x)) return CautareBinara(m + 1, dr, comanda, x);
	else return CautareBinara(st, m - 1, comanda, x);
}

int main() {
	int i, comanda, x;
	
	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", &comanda, &x), printf("%d\n", CautareBinara(1, n, comanda, x));
	
	return 0;
}