#include <stdio.h>
#include <stdlib.h>

int bs0(int *v, int x, int a, int b)
{
	if (a > b) return -1;
	int c = (a + b) / 2;
	if (v[c] == x)
	{
		while (v[c] == x) c++;
		return c - 1;
	}
	if (v[c] < x) return bs0(v, x, c + 1, b);
	if (v[c] > x) return bs0(v, x, a, c - 1);
}

int bs1(int *v, int x, int a, int b)
{
	int c = (a + b) / 2;
	if (v[c] <= x && v[c + 1] > x)
		return c;
	if (v[c] <= x) return bs1(v, x, c + 1, b);
	if (v[c] > x) return bs1(v, x, a, c - 1);
}

int bs2(int *v, int x, int a, int b)
{
	int c = (a + b) / 2;
	if (v[c] >= x && v[c - 1] < x)
		return c;
	if (v[c] < x) return bs2(v, x, c + 1, b);
	if (v[c] >= x) return bs2(v, x, a, c - 1);
}

int main()
{
	FILE *f, *g;
	int n, m, i, op, x;
	
	f = fopen("cautbin.in", "r");
	fscanf(f, "%d", &n);

	int *v = (int *)malloc(sizeof(int) * n);
	
	for (i = 0; i < n; i++)
		fscanf(f, "%d", &v[i]);

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

	g = fopen("cautbin.out", "w");

	for (i = 0; i < m; i++)
	{
		fscanf(f, "%d", &op);
		fscanf(f, "%d", &x);
		if (op == 0) fprintf(g, "%d\n", bs0(v, x, 0, n - 1) + 1);
		if (op == 1) fprintf(g, "%d\n", bs1(v, x, 0, n - 1) + 1);
		if (op == 2) fprintf(g, "%d\n", bs2(v, x, 0, n - 1) + 1);
	}

	fclose(f);
	fclose(g);

	return 0;
}