#include <stdio.h>

int N, M;
int a[100020]; // sirul de numere ordonat



int cautbin0(int x)
{
	int lo = 0;
	int hi = N - 1;
	int mid = 0;
	while (lo <= hi)
	{
		mid = lo + (hi - lo) / 2;
		if 		(x < a[mid])	hi = mid - 1;
		else if (x > a[mid]) 	lo = mid + 1;
		else					break;
	}
	if (lo > hi)	return -1;
	mid = lo < hi ? lo : hi;
	while (mid < N - 1 && x == a[mid + 1]) 
		++mid;
	return mid + 1;		
}

int cautbin1(int x)
{
	int lo = 0;
	int hi = N - 1;
	int mid = 0;
	while (lo <= hi)
	{
		mid = lo + (hi - lo) / 2;
		if 		(x < a[mid])	hi = mid - 1;
		else if (x > a[mid]) 	lo = mid + 1;
		else					break;
	}

	mid = lo < hi ? lo : hi;
	while (mid < N - 1 && a[mid + 1] <= x)	
		++mid;
	return mid + 1;
}


int cautbin2(int x)
{
	int lo = 0;
	int hi = N - 1;
	int mid = 0;
	while (lo <= hi)
	{
		mid = lo + (hi - lo) / 2;
		if 		(x < a[mid])	hi = mid - 1;
		else if (x > a[mid]) 	lo = mid + 1;
		else					break;
	}

	mid = lo > hi ? lo : hi;	
	while (mid > 0 && a[mid - 1] >= x)	
		--mid;
	return mid + 1;
}


int main(void)
{
	int i = 0;
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);

	scanf("%d", &N);
	for (i = 0; i < N; ++i)	
		scanf("%d", &a[i]);
	scanf("%d", &M);

	while (M)
	{
		int i, x;
		scanf("%d %d\n", &i, &x);

		switch(i)
		{
			case 0: printf("%d\n", cautbin0(x)); break;
			case 1: printf("%d\n", cautbin1(x)); break;
			case 2: printf("%d\n", cautbin2(x)); break;					
		}

		--M;
	}
	return 0;
}