#include <stdio.h>

void init()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
}
long int cautBin0(long int *vec, long int len, long int x)
{
	long int mid, st, dr;
	st = 1;
	dr = len;
	while (st <= dr)
	{
		mid = (st + dr) / 2;
		if(vec[mid] <= x)
			st = mid + 1;
		else 
			dr = mid - 1;
	}
	mid = (st + dr) / 2;
	if(vec[mid] > x) mid--;
	if(vec[mid] == x) return mid;
	return -1;
}
long int cautBin1(long int *vec, long int len, long int x)
{
	long int mid, st, dr;
	st = 1;
	dr = len;
	while (st < dr)
	{
		mid = (st + dr) / 2;
		if(vec[mid] <= x)
			st = mid + 1;
		else 
			dr = mid;
	}
	mid = (st + dr) / 2;
	if(vec[mid] > x) mid--;
	return mid;
}
long int cautBin2(long int *vec, long int len, long int x)
{
	long int mid, st, dr;
	st = 1;
	dr = len;
	while (st < dr)
	{
		mid = (st + dr) / 2;
		if(vec[mid] < x)
			st = mid + 1;
		else 
			dr = mid;
	}
	mid = (st + dr) / 2;
	if(vec[mid] > x) mid++;
	return mid;
}

int main()
{
	init();
	
	long int vec[100001],i,n,m,x,tmp;
	scanf("%lu",&n);
	for(i = 1;i <= n;i++)
		scanf("%lu",&vec[i]);
	scanf("%lu",&m);
	for(i = 0; i < m;i++)
	{
		scanf("%lu",&tmp);
		switch(tmp)
		{
		case 0:
			scanf("%lu",&x);
			printf("%lu\n",cautBin0(vec,n,x));
			break;
		case 1:
			scanf("%lu",&x);
			printf("%lu\n",cautBin1(vec,n,x));
			break;
		case 2:
			scanf("%lu",&x);
			printf("%lu\n",cautBin2(vec,n,x));
			break;
		default : printf("-1\n");
		}
	}
	return 0;
}