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

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

	c = (a + b) / 2;
	if (v[c] > x) c--;
	if (v[c] == x) return c;
	return -1;
}

int bs1(int *v, int x, int a, int b)
{
	int c;
	while (a < b)
	{
		c = (a + b) / 2;
		if (v[c] <= x)
			a = c + 1;
		else b = c;
	}

	c = (a + b) / 2;
	if (v[c] > x) c--;
	return c;
}

int bs2(int *v, int x, int a, int b)
{
	int c;

	while (a < b)
	{
		c = (a + b) / 2;
		if (v[c] < x)
			a = c + 1;
		else b = c;
	}

	c = (a + b) / 2;
	if (v[c] < x) c--;
	return c;
}

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 + 1));
	
	for (i = 1; 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, 1, n));
		if (op == 1) fprintf(g, "%d\n", bs1(v, x, 1, n));
		if (op == 2) fprintf(g, "%d\n", bs2(v, x, 1, n));
	}

	fclose(f);
	fclose(g);

	return 0;
}