#include <stdio.h>
#include <stdlib.h>

int firstBinarySearch(int * v, int n, int number) {
	int low = 1;
	int high = n - 1;
	int mid = -1;

	while (low <= high) {
		mid = low + (high - low) / 2;
		if (v[mid] <= number) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	mid = low + (high - low) / 2;

	// if the mid is off by one
	if (v[mid] > number) {
		mid--;
	}

	// if the number was found
	if (v[mid] == number) {
		return mid;
	}

	// the number was not found
	return -1;
}

int secondBinarySearch(int * v, int n, int number) {
	int low = 1;
	int high = n - 1;
	int mid = -1;

	while (low < high) {
		mid = low + (high - low) / 2;
		if (v[mid] <= number) {
			low = mid + 1;
		} else {
			high = mid;
		}
	}
	mid = low + (high - low) / 2;

	// if the mid is off by one
	if (v[mid] > number) {
		mid--;
	}

	// if the number was found	
	return mid;
}

int thirdBinarySearch(int * v, int n, int number) {
	int low = 1;
	int high = n - 1;
	int mid = -1;

	while (low < high) {
		mid = low + (high - low) / 2;
		if (v[mid] < number) {
			low = mid + 1;
		} else {
			high = mid;
		}
	}
	mid = low + (high - low) / 2;

	// if the mid is off by one
	if (v[mid] < number) {
		mid++;
	}

	// if the number was found	
	return mid;
}

int main(int argc, char ** argv) {
	int n; // array length
	int i, m, command, number, test;
	int * v;
	FILE * testFile;

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

	// read the size of the array
	test = scanf("%d", &n);
	v = (int *)malloc(sizeof(int) * n);
	if (!v) {
		return -1;
	}

	// read the elements of the array
	for (i = 0; i < n; i++) {
		test = scanf("%d", &v[i]);
	}

	// read the number of querries
	test = scanf("%d", &m);
	for (i = 0; i < 3; i++) {
		test = scanf("%d", &command);
		test = scanf("%d", &number);

		switch(command) {
			case 0 :
				printf("%d\n", firstBinarySearch(v, n, number));
				break;
			case 1 :
				printf("%d\n", secondBinarySearch(v, n, number));
				break;
			case 2 :
				printf("%d\n", thirdBinarySearch(v, n, number));
				break;
			default :
				printf("ERROR! Bad input...");
				break;
		}
	}

	if (test < 0 || testFile == NULL) {
		printf("Strange errors happened!");
	}

	free(v);

	return 0;
}