#include <stdio.h>
#define NMAX 100000

int cauta0(int x, int* tab, int n) {
	int l = 0;
	int h = n;
	int m = (l + h)/2;
	while(h-l > 1) {
		if(tab[m] > x) {
			h = m;
		} else {
			l = m;
		}
		m = (l + h)/2;
	}
	if(tab[l] == x) {
		return l + 1;
	} else {
		return -1;
	}
}

int cauta1(int x, int* tab, int n) {
	int l = 0;
	int h = n;
	int m = (l + h)/2;
	while(h-l > 1) {
		if(tab[m] > x) {
			h = m;
		} else {
			l = m;
		}
		m = (l + h)/2;
	}
	if(tab[l] == x) {
		return l + 1;
	} else {
		return h + 1;
	}
}

int cauta2(int x, int* tab, int n) {
	int l = 0;
	int h = n;
	int m = (l + h)/2;
	while(h-l > 1) {
		if(tab[m] < x) {
			l = m;
		} else {
			h = m;
		}
		m = (l + h)/2;
	}
	if(tab[h] == x) {
		return h + 1;
	} else {
		return l + 1;
	}
	
}

int main() {
	FILE* fin = fopen("cautbin.in", "r");
	int n,m;
	int i;
	int t[NMAX];
	fscanf(fin, "%d\n", &n);
	for(i=0; i<n; i++) {
		fscanf(fin, "%d", &t[i]);
	}
	fscanf(fin, "%d\n", &m);
	
	int type, x;
	FILE* fout = fopen("cautbin.out", "w");
	for(i=0; i<m; i++) {
		fscanf(fin, "%d%d", &type, &x);
		int res;
		if(type == 0) {
			res = cauta0(x, t, n);
		} else if(type == 1) {
			res = cauta1(x, t, n);
		} else {
			res = cauta2(x, t, n);
		}
		fprintf(fout, "%d\n", res);
	}
	
	fclose(fin);
	fclose(fout);
	return 0;
}