#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

// cea mai mare pozitie pe care se afla x sau - 1 daca nu exista in sir
int binary_zero(int x, int* v, int n) {
	int result = -1;
	int i = 0, step = 1;
	for (;step < n; step <<= 1);
	for (; step; step >>= 1) {
		if (i + step < n) {
			if (v[i + step] == x) {
				result = i + step;
				i += step;
			}
			else if (v[i + step] < x) {
				i += step;
			}
		}
	}
	return result + 1;
}

// cea mai mare pozitie pe care se afla un element cu valoarea <= x
int binary_one(int x, int* v, int n) {
	int i = 0, step = 1;
	for (; step < n; step <<= 1);
	for (; step; step >>= 1) {
		if (i + step < n && v[i + step] <= x) {
			i += step;
		}
	}
	return i + 1;
}

// cea mai mica pozitie pe care se afla un element cu valoarea >= x
int binary_two(int x, int* v, int n) {
	int i = n, step = 1;
	for (; step < n; step <<= 1);
	for (; step; step >>= 1) {
		if (i - step >= 0) {
			if (v[i - step] >= x) {
				i -= step;
			}
		}
	}
	return i + 1;
}

int main() {

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

	int n, m;
	scanf("%i", &n);
	int* v = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++) {
		scanf("%i", v + i);
	}
	scanf("%i", &m);
	for (int i = 0; i < m; i++) {
		int cod, val;
		scanf("%i", &cod);
		scanf("%i", &val);
		if (cod == 0) {
			printf("%i\n", binary_zero(val, v, n));
		}
		else if (cod == 1) {
			printf("%i\n", binary_one(val, v, n));
		}
		else if (cod == 2) {
			printf("%i\n", binary_two(val, v, n));
		}
	}

	fclose(stdin);
	fclose(stdout);
	return 0;

}