#include <stdio.h>
long v[100005],n;
long ask0(long x)
	{
	long p=0,i,li,ls,mid;
	li=1;
	ls=n;
	mid=(li+ls)/2;
	while (li<=ls)
		{
		if (v[mid]<=x)
			{
			if (v[mid]==x) p=1;
			li=mid+1;
			mid=(li+ls)/2;
			}
		else
			{
			ls=mid-1;
			mid=(li+ls)/2;
			}
		}
	if (p) return mid;
	else return -1;
	}

long ask1(long x)
	{
	long i,li,ls,mid;
	li=1;
	ls=n;
	mid=(li+ls)/2;
	while (li<=ls)
		{
		if (v[mid]<=x)
			{
			i=mid;
			li=mid+1;
			mid=(li+ls)/2;
			}
		else
			{
			ls=mid-1;
			mid=(li+ls)/2;
			}
		}
	return i;
	}
long ask2(long x)
	{
	long i,li,ls,mid;
	li=1;
	ls=n;
	mid=(li+ls)/2;
	while (li<=ls)
		{
		if (v[mid]>=x)
			{
			i=mid;
			ls=mid-1;
			mid=(li+ls)/2;
			}
		else
			{
			li=mid+1;
			mid=(li+ls)/2;
			}
		}
	return i;
	}
int main()
{
long i,m,j;
int q;
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%ld",&n);
for (i=1;i<=n;i++)
	scanf("%ld",&v[i]);
scanf("%ld",&m);
for (i=1;i<=m;i++)
	{
	scanf("%d %ld",&q,&j);
	if (!q) printf("%ld\n",ask0(j));
	else
	if (q==1) printf("%ld\n",ask1(j));
	else
	printf("%ld\n",ask2(j));
	}
return 0;
}