#include <iostream>
#include <stdio.h>
/*
int binary_search(int v[], int x, int left, int right) {
	
	int mid = left + (right - left) / 2;
	
	if (v[mid] == x && left > right) {
		return mid;
	}
	
	else if (x < v[mid]) {
		right = mid - 1;
		binary_search(v, x, left, right);
	}
	else if (x >= v[mid]) {
		left = mid + 1;
		binary_search(v, x, left, right);
	}
	else {
		return -1;
	}


}
*/

const int NMAX = 300009;

int v[NMAX];

int binary_search0(int v[], int x, int N) {
	
	int pos ; int step;
	
	for(step = 1; step <= N ; step *= 2);
	
	for(pos = 1; step > 0; step /= 2)
		if(pos + step <= N && v[pos + step] <= x)
			pos += step;
			
	if(v[pos] == x) return pos;
	return -1;
}

int binary_search1(int v[], int x, int N) {
	
	int pos ; int step;
	
	for(step = 1; step <= N ; step *= 2);
	
	for(pos = 1; step > 0; step /= 2)
		if(pos + step <= N && v[pos + step] <= x)
			pos += step;
			
	return pos;
}


int binary_search2(int v[], int x, int N) {
	
	int pos ; int step;
	
	step = (1 << 23);
	
	for(pos = 1; step > 0; step /= 2)
		if(pos + step <= N && v[pos + step] < x)
			pos += step;
			
	return pos + 1;
}

int main() {
	
	int N, M, test, x;
	FILE *fin = fopen("cautbin.in", "r");
	FILE *fout = fopen("cautbin.out", "w");
	
	fscanf(fin, "%d", &N);
	
	for (int i = 1; i <= N; i++) {
		fscanf(fin, "%d", &v[i]);
	}
	
	fscanf(fin, "%d", &M);

	for (int i = 0; i < M; i++) {
	
		fscanf(fin, "%d %d", &test, &x);
		
		
		
		if (test == 0) {
			fprintf(fout, "%d\n", binary_search0(v, x, N));
			
		}
		else if (test == 1) { // lower bound
			fprintf(fout, "%d\n", binary_search1(v, x, N));
			
			
				
		}
		else if (test == 2) { // upper bound
			fprintf(fout, "%d\n", binary_search2(v, x, N));
			
		}
	
	}
	
	fclose(fin);
	fclose(fout);
	
}