#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int sir[100001];

int bsearch0(int stg, int dr, int key) {

	if (stg > dr) {

		return -1;
	}

	int mij = (stg + dr) / 2;

	if (sir[mij] > key) {

		return bsearch0(1, mij - 1, key);
	}
	else if (sir[mij] < key) {

		return bsearch0(mij + 1, dr, key);
	}
	else {

		if (sir[mij + 1] == key) {

			return bsearch0(mij + 1, dr, key);
		}
		else {

			return mij;
		}
	}
}

int bsearch1(int stg, int dr, int key) {

	if (stg > dr) {

		return -1;
	}

	int mij = stg + (dr - stg) / 2;

	if (sir[mij] == key) {

		if (sir[mij + 1] == key) {

			return bsearch1(mij + 1, dr, key);
		}
		else {

			return mij;
		}
	}
	else if (sir[mij] > key) {

		return bsearch1(stg, mij - 1, key);
	}
	else { 

		if (sir[mij + 1] > key || mij + 1 > dr) {

			return mij;
		}
		else {

			return bsearch1(mij + 1, dr, key);
		}
	}
}

int bsearch2(int stg, int dr, int key) {

	if (stg > dr) {

		return -1;
	}

	int mij = stg + (dr - stg) / 2;

	if (sir[mij] == key) {

		if (sir[mij - 1] == key) {

			return bsearch2(stg, mij - 1, key);
		}
		else {

			return mij;
		}
	}
	else if(sir[mij] > key){

		if (sir[mij - 1] < key || mij - 1 < stg) {

			return mij;
		}
		else {

			return bsearch2(stg, mij - 1, key);
		}
	}
	else { 

		return bsearch2(mij + 1, dr, key);
	}
}

int main() {

	FILE* ip;
	FILE* op;

	ip = fopen("cautbin.in", "r");
	if (ip == NULL) {

		perror("Cannou open input file");
		return 1;
	}

	op = fopen("cautbin.out", "w");
	if (op == NULL) {

		perror("Cannou open output file");
		return 1;
	}

	int n;
	fscanf(ip, "%d", &n);

	for (int i = 1; i <= n; i++) {

		fscanf(ip, "%d", &sir[i]);
	}

	int m;
	fscanf(ip, "%d", &m);

	for (int i = 0; i < m; i++) {

		int intrebare, k;
		fscanf(ip, "%d%d", &intrebare, &k);

		if (intrebare == 0) {

			fprintf(op, "%d\n", bsearch0(1, n, k));
		}
		else if (intrebare == 1) {

			fprintf(op, "%d\n", bsearch1(1, n, k));
		}
		else {

			fprintf(op, "%d\n", bsearch2(1, n, k));
		}
	}

	fclose(ip);
	fclose(op);

	return 0;
}