#include <stdio.h>
#define MAXN 100002

int a[MAXN];
int n;

void bsearch(int key)
{
	int lo = 1,hi = n,mid =(lo+hi)/2,i;
	while (hi>lo)
	{
		if (a[mid] == key)
		{
			for (i=mid;a[i] == key;i++);
			printf("%d\n",i-1);
			return;
		}
		else
		{
			if (a[mid]>key)
			{
				hi = mid-1;
				mid = (hi+lo) / 2;
			}
			else
			{
				lo = mid +1;
				mid = (hi+lo) / 2;
			}
		}
	}
	printf("-1\n");
}

void bsearch2(int key)
{
	int lo = 1,hi = n,mid =(lo+hi)/2;
	while (hi>lo)
	{
		if (a[mid] > key)
		{
			hi = mid - 1;
			mid = (hi+lo) /2;
		}
		else 
		{
			if (a[mid+1]<=key)
			{
				lo = mid+1;
				mid = (hi+lo) / 2;
			}
			else
			{
				printf("%d\n",mid);
				return;
			}

		}
	}
	printf("%d\n",mid);
}

void bsearch3(int key)
{
	int lo = 1,hi = n,mid =(lo+hi)/2;
	while (hi>lo)
	{
		if (a[mid] < key)
		{
			lo = mid + 1;
			mid = (hi+lo) /2;
		}
		else 
		{
			if (a[mid-1]>=key)
			{
				hi = mid - 1;
				mid = (hi+lo) / 2;
			}
			else
			{
				printf("%d\n",mid);
				return;
			}

		}
	}
	printf("%d\n",mid);
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	int m,i,op,key;
	
	scanf("%d",&n);
	for (i=0;i<n;i++)
	{
		scanf("%d",&a[i+1]);
	}

	scanf("%d",&m);

	for (i=0;i<m;i++)
	{
		scanf("%d%d",&op,&key);
		switch(op)
		{
		case 0:bsearch(key);  break;
		case 1:bsearch2(key); break;
		case 2:bsearch3(key); break;
		}
	}

	return 0;
}