#include <stdio.h>

#define NMAX 100000

unsigned int data[NMAX];

int exact_search_last_pos(unsigned int val, unsigned int N) {
	int left, right, middle, result;
	bool found;

	left = 0;
	right = N - 1;
	found = false;
	while (left <= right) {
		middle = (left + right) / 2;
		if (data[middle] == val) {
			found = true;

			// find the last pos
			while (data[middle+1] == val)
			{
				middle ++;
			}
			break;
		} else {
			if (val < data[middle]) {
				right = middle - 1;
			} else {
				left = middle + 1;
			}
		}
	}

	if (found) {
		result = middle + 1; // positions are numbered from 1
	} else {
		result = -1;
	}

	return result;
}

int inexact_search_last_pos(unsigned int val, unsigned int N) {
	int left, right, middle, result;
	bool found;

	left = 0;
	right = N - 1;
	found = false;

	while (left <= right) {
		middle = (left + right) / 2;
		if (data[middle] == val) {
			found = true;

			// find the last pos
			while (data[middle+1] == val)
			{
				middle ++;
			}
			break;
		} else {
			if (val < data[middle]) {
				right = middle - 1;
			} else {
				left = middle + 1;
			}
		}
	}

	if (found) {
		result = middle + 1; // positions are numbered from 1
	} else {
		result = right + 1; // positions are numbered from 1
	}

	return result;
}

int inexact_search_first_pos(unsigned int val, unsigned int N) {
	int left, right, middle, result;
	bool found;

	left = 0;
	right = N - 1;
	found = false;

	while (left <= right) {
		middle = (left + right) / 2;
		if (data[middle] == val) {
			found = true;

			// find the last pos
			while (data[middle-1] == val)
			{
				middle --;
			}
			break;
		} else {
			if (val < data[middle]) {
				right = middle - 1;
			} else {
				left = middle + 1;
			}
		}
	}

	if (found) {
		result = middle + 1; // positions are numbered from 1
	} else {
		result = left + 1; // positions are numbered from 1
	}

	return result;
}

int main()
{
	unsigned int N, M, opt, val;
	FILE *fin, *fout;
	
	fin = fopen("cautbin.in", "r");
	fout = fopen("cautbin.out", "w");

	fscanf(fin, "%u", &N);
	for(unsigned int i = 0; i < N; i++){
		fscanf(fin, "%u", &data[i]);
	}

	fscanf(fin,"%u", &M);
	for(unsigned int i = 0; i < M; i++) {
		fscanf(fin, "%u%u", &opt, &val);

		switch (opt)
		{
		case 0:
			fprintf(fout, "%d\n", exact_search_last_pos(val, N));
			break;
		case 1:
			fprintf(fout, "%d\n", inexact_search_last_pos(val, N));
			break;
		case 2:
			fprintf(fout, "%d\n", inexact_search_first_pos(val, N));
			break;
		default:
			break;
		}
	}

	fclose(fin);
	fclose(fout);

	return 0;
}