#include<cstdio>
FILE *in = fopen ("cautbin.in", "r"), *out = fopen ("cautbin.out", "w");

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

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

int main(){
	fscanf (in, "%d", &n);
	int i, tip, val;
	for (i = 1; i <= n; i++) fscanf (in, "%d", &v[i]);
	
	fscanf (in, "%d", &m);
	for (i = 1; i <= m; i++){
		fscanf (in, "%d %d", &tip, &val);
		fprintf (out, "%d\n", CautaPoz(1, n, val, tip));
	}
	return 0;
}