#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 (v[mid]!=x&&li<=ls)
		{
		if (v[mid]>x)
			{
			ls=mid;
			mid=(li+ls)/2;
			}
		else
		if (v[mid]<x)
			{
			li=mid;
			mid=(li+ls)/2;
			}
		else
		p=1;
      }
   if (v[mid]==x) p=1;
	if (p)
		{
		while (v[mid]==v[mid+1]&&mid<n)
			mid++;
		return mid;
		}
	else return -1;
   }
long ask1(long x)
	{
	long i,li,ls,mid;
	li=1;
	ls=n;
	mid=(li+ls)/2;
	while (v[mid]>x&&li<=ls)
		{
		if (v[mid]>x)
			{
			ls=mid;
			mid=(li+ls)/2;
			}
		else
			{
			li=mid;
			mid=(li+ls)/2;
			}
		}
	while (v[mid]<=x)
		mid++;
	return mid-1;
	}
long ask2(long x)
	{
	long i,li,ls,mid;
	li=1;
	ls=n;
	mid=(li+ls)/2;
	while (v[mid]<x&&li<=ls)
		{
		if (v[mid]<x)
			{
			li=mid;
			mid=(li+ls)/2;
			}
		else
			{
			ls=mid;
			mid=(li+ls)/2;
			}
		}
	while (v[mid]>=x)
		mid--;
	return mid+1;
	}
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;
}