#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) {
			return mid;
		} else if (x > v[mid]) {
			st = mid+1;
		} else {
			dr = mid-1;
		}
	}

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


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

	return st;

}

int BS2 () {
	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;
		}
	}

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

	while (x > v[dr]) {
		dr++;
	}

	return dr;
}


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;
}