#include <stdio.h>
#define max 100005

int i,y,x,n,m,r,mid,st,dr;
int v[max];

int BS0 () {
	st = 1;
	dr = n;

	mid = (st + dr) / 2;

	while (st <= dr) {
		mid = (st + dr) / 2;

		if (v[mid] == x) {
			return mid;
		} else if (x > v[mid]) {
			st = mid+1;
		} else {
			dr = mid-1;
		}
	}

	return -1;
}

int BS1 () {
	st = 1;
	dr = n;

	mid = (st + dr) / 2;

	while (st <= dr) {
		mid = (st + dr) / 2;

		if (v[mid] == x) {
			while ((v[mid-1] <= x) && (v[mid] > x) && ((mid-1) >= 1)) {
				mid--;
			}

			while ((v[mid+1] <= x) && ((mid+1) <= n)) {
				mid++;
			}

			return mid;
		} else if (x > v[mid]) {
			st = mid+1;
		} else {
			dr = mid-1;
		}
	}

	if (st < 1) st=1;
	if (st > n) st=n;

	while ((v[st-1] <= x) && (v[st] > x) && ((st-1) >= 1)) {
		st--;
	}

	while ((v[st+1] <= x) && ((st+1) <= n)) {
		st++;
	}

	return st;
}

int BS2 () {
	st = 1;
	dr = n;

	mid = (st + dr) / 2;

	while (st <= dr) {
		mid = (st + dr) / 2;

		if (v[mid] == x) {
			while ((v[mid+1] >= x) && (v[mid] < x) && ((mid+1) <= n)) {
				mid++;
			}

			while ((v[mid-1] >= x) && ((mid-1) >= 1 )) {
				mid--;
			}

			return mid;
		} else if (x > v[mid]) {
			st = mid+1;
		} else {
			dr = mid-1;
		}
	}

	if (st < 1) st=1;
	if (st > n) st=n;

	while ((v[st+1] >= x) && (v[st] < x) && ((st+1) <= n)) {
		st++;
	}

	while ((v[st-1] >= x) && ((st-1) >= 1 )) {
		st--;
	}

	return st;
}


int main () {
	FILE * in  = fopen("cautbin.in", "r");
	FILE * out = fopen("cautbin.out", "w");

	fscanf(in, "%d", &n);

	for (i=1; i<=n; i++) {
		fscanf(in, "%d", &v[i]);
	}

	fscanf(in, "%d", &m);

	for (; m>0; m--) {
		fscanf(in, "%d %d", &y, &x);

		switch (y) {
			case 0:
				r = BS0();
				break;
			case 1:
				r = BS1();
				break;
			case 2:
				r = BS2();
				break;
		}

		fprintf(out, "%d\n", r);
	}

	fclose(in);
	fclose(out);
	return 0;
}