#include <stdio.h>
#include <stdlib.h>

int cautBin0(int *vec,int len,int x)
{
	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;
}
int cautBin1(int *vec, int len, int x)
{
	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 cautBin2(int *vec, int len, int x)
{
	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()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	int vec[100001],i,n,m,x,tmp;
	scanf("%d",&n);
	for(i = 1;i <= n;i++)
		scanf("%d",&vec[i]);
	scanf("%d",&m);
	for(i = 0; i < m;i++)
	{
		scanf("%d",&tmp);
		switch(tmp)
		{
		case 0:
			scanf("%d",&x);
			printf("%d\n",cautBin0(vec,n,x));
			break;
		case 1:
			scanf("%d",&x);
			printf("%d\n",cautBin1(vec,n,x));
			break;
		case 2:
			scanf("%d",&x);
			printf("%d\n",cautBin2(vec,n,x));
			break;
		default : printf("-1\n");
		}
	}
	return 0;
}