#include <cstdio>

using namespace std;
int *a, n;


int cautBin(int val, int type) {
	int step;
	for (step = 1; step < n; step<<=1);
	int i;
	int maxLg = step;
	for (i = 0; step; step>>=1){
		if (i + step < n && a[i + step] <= val){
			i +=step;
		}
	}

	if ((a[i] != val)&&(type == 0)) return -1;
	else if (type == 2) {
		for (i = n; maxLg; maxLg>>=1){
			if ( i - maxLg >= 0 && a[i - maxLg] >= val ) i-= maxLg;
		}
		return i+1;		
	}	

	return i+1;
}




int main() {

	freopen("cautbin.in","r", stdin);
	freopen("cautbin.out","w", stdout);

	int t;
	scanf("%d\n", &n);
	a = new int[n];
	int i;
	for (i = 0; i < n; i++)
		scanf("%d",&a[i]);
	scanf("%d", &t);

	int type, nr;
	for (i = 0; i < t; i++) {
		scanf("%d %d", &type, &nr);
		printf("%d\n", cautBin(nr, type));
	}

	delete []a;

	return 0;
}