#include <stdio.h>

typedef	struct instructiuni
{
	int x, y;
}instr;

instr s[100000];

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

	f = fopen("cautbin.in", "r");
	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", &s[i].x, &s[i].y);
	fclose(f);
}

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

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

void	output(int n, int m, int *a)
{
	FILE *g; int i;

	g = fopen("cautbin.out", "w");
	for (i = 0; i < m; i++)
	{
		if (s[i].x == 0) fprintf(g, "%d\n", cautare(n, m, a, s[i].y));
		else if (s[i].x == 1) fprintf(g, "%d\n", cautare1(n, m, a, s[i].y));
		else if (s[i].x == 2) fprintf(g, "%d\n", cautare2(n, m, a, s[i].y));
	}
	fclose(g);
}

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

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