#include <stdio.h>

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

	while (start <= end)
	{
		mid = (start + end) / 2;
		if (a[mid] >= k) start = mid + 1;
		else end = mid - 1;
		if (a[mid] == k) { id = mid + 1; }
	}

	return (id);
}

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

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

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

	while (start <= end)
	{
		mid = (start + end) / 2;
		//printf("%d %d %d\n", start, mid, end);
		if (a[mid] >= k) end = mid - 1;
		else start = mid + 1;
		if (a[mid] >= k && mid < id) id = mid;
	}
	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);
}