#include <stdio.h>

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



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


int cautbin0(int x)
{
	int i = cautbin(x);	
	if (i == -1)	return -1;
	while (i < N - 1 && x == a[i + 1]) 
		++i;
	return i + 1;		
}


int cautbin1(int x)
{
	int i = cautbin(x);	
	while (i < N - 1 && a[i + 1] <= x)	
		++i;
	return i + 1;
}


int cautbin2(int x)
{
	int i = cautbin(x);	
	while (i > 0 && a[i - 1] >= x)	
		--i;
	return i + 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;
}