#include <stdio.h>

int	cautare(int n, int m, int *a, int k)
{
	int start = 0, end = n - 1, mid;

	while (start <= end)
	{
		mid = (start + end) / 2;
		//printf("%d %d %d\n", start, mid, end);
		if (a[mid] < k) start = mid + 1;
		else if (a[mid] > k) end = mid - 1;
		else return (mid);
	}
	return (-1);
}

int	cautare1(int n, int m, int *a, int k)
{
	int start = 0, end = n - 1, mid, id = -1;

	while (start <= end)
	{
		mid = (start + end) / 2;
		//printf("%d %d %d\n", start, mid, end);
		if (a[mid] <= k) { start = mid + 1; id = mid; }
		else end = mid - 1;
	}
	return (id + 1);
}

int	cautare2(int n, int m, int *a, int k)
{
	int start = 0, end = n - 1, mid, id = n;

	while (start <= end)
	{
		mid = (start + end) / 2;
		//printf("%d %d %d %d\n", start, mid, end, a[mid - 1]);
		//getchar();
		if (a[mid] <= k) { end = mid - 1; id = mid; }
		else start = mid + 1;
	}
	return (id + 1);
}

void	readfrom(int *n, int *m, int *a)
{
	FILE *f, *g; int i, k, j;

	f = fopen("cautbin.in", "r");
	g = fopen("cautbin.out", "w");
	fscanf(f, "%d", n);
	for (i = 0; i < *n; i++)
		fscanf(f, "%d", &a[i]);
	fscanf(f, "%d", m);
	for (i = 0; i < *m; i++)
	{
		fscanf(f, "%d %d", &k, &j);
		if (k == 0) fprintf(g, "%d\n", cautare(*n, *m, a, j));
		else if (k == 1) fprintf(g, "%d\n", cautare1(*n, *m, a, j));
		else if (k == 2) fprintf(g, "%d\n", cautare2(*n, *m, a, j));
	}
	fclose(f);
	fclose(g);
}

int	main(void)
{
	int n, m, a[100000];

	readfrom(&n, &m, a);
	return (0);
}