#include <iostream>
#include <stdio.h>

using namespace std;

int m, n, v[100005];

inline int bsearch0 (int x) {
	int mid, l = 0, r = n;
	
	while (r - l > 1) {
		mid = (l + r) / 2;
		
		if (x < v[mid]) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	
	if (v[mid-1] == x) {
		return mid;
	}
	
	return -1;
}

inline int bsearch1 (int x) {
	int mid, l = 0, r = n;
	
	while (r - l > 1) {
		mid = (l + r) / 2;
		
		if (x < v[mid]) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	
	return mid;
}

inline int bsearch2 (int x) {
	int mid, l = 0, r = n;
	
	while (r - l > 1) {
		mid = (l + r) / 2;
		
		if (x < v[mid]) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	
	return mid;
}
	
int main (void) {
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	
	scanf("%d", &m);
	for (int i = 0; i < m; ++i) {
		int x, c;
		scanf("%d %d", &c, &x);
		
		if (c == 0) {
			printf("%d\n", bsearch0(x));
		} else if (c == 1) {
			printf("%d\n", bsearch1(x));
		} else {
			printf("%d\n", bsearch2(x));
		}
	}
	
	return 0;
}