#include <stdio.h>

#define MAXSIZE 100001

int N, E[MAXSIZE];

int search_0(int x)
{
	int left = 1, right = N, mid = 0;

	while (left < right) 
	{
		mid = left + (right - left) / 2;

		if (E[mid] <= x) 
			left = mid + 1;
		else 
			right = mid - 1;
	}
	
	mid = left;
	if (E[mid] > x) --mid;	
    return E[mid] == x ?  mid : -1;
}

int search_1(int x)
{
	int left = 1, right = N, mid = 0;

	while (left < right) 
	{
		mid = left + (right - left) / 2;

		if (E[mid] <= x) 
			left = mid + 1;
		else 
			right = mid - 1;
	}
	
	mid = left + (right - left) / 2;	
    return E[mid] > x ? --mid : mid;
}

int search_2(int x)
{
	int left = 1, right = N, mid = 0;

	while (left < right) 
	{
		mid = left + (right - left) / 2;

		if (E[mid] < x) 
			left = mid + 1;
		else 
			right = mid - 1;
	}
	
	mid = left + (right - left) / 2;	
    return E[mid] < x ? ++mid : mid;
}

int main()
{
	int i;
	int t, x, r;
	int M;

	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	
	scanf("%d", &N);
	for (i = 1; i <= N; ++i)
		scanf("%d", E + i);

	scanf("%d", &M);
	while (M--)
	{
		scanf("%d %d", &t, &x);
		switch(t)
		{
			case 0: r = search_0(x); break;
			case 1: r = search_1(x); break;
			case 2: r = search_2(x); break;
			default: r = -1;
		}
		printf("%d\n", r);
	}
	
	return 0;
}