#include <cstdio>
using namespace std;

#define NMAX 100001
int n, m, A[NMAX];

int answer01(int val, int type) {
	int low=1, high=n, mid;
	while (low <= high){
		mid = low + (high-low)/2;
		if (A[mid] <= val) {
			low = mid+1;
		}
		else high = mid-1;
	}
	if (type == 1 || A[low-1] == val) return low-1;
	return -1;
}

int answer2(int val) {
	int low=1, high=n, mid;
	while (low <= high){
		mid = low + (high-low)/2;
		if (A[mid] < val) {
			low = mid+1;
		}
		else high = mid-1;
	}
	return low;
}

int main() {
	int i, type, x, res;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++) {
		scanf("%d",&A[i]);
	}
	scanf("%d",&m);
	for (i=1;i<=m;i++) {
		scanf("%d %d",&type,&x);
		if (type < 2) {
			res = answer01(x, type);
		}
		else res = answer2(x);
		printf("%d\n",res);
	}
	return 0;
}