#include <stdio.h>

int i,m,n,x,v[100001],r,l=1,a,b,y,t,z,j;

int cb1(int x)
{
	int m=l+(l+r)/2;
	while (v[m]!=x && l<r)
		  {
		   if (v[m]<x) l=m+1;
		   else r=m-1;
		   m=l+(l+r)/2;
		  }
	if (v[m]==x) return m;
	else return -1;
}

int cb2(int x)
{
	int m=l+(l+r)/2;
	while (v[m]!=x && l<r)
		  {
		   if (v[m]<x) l=m+1;
		   else r=m-1;
		   m=l+(l+r)/2;
		  }
	return m;
}

int cb3(int x)
{
  
	while (l<r)
		  {
		   m=(l+r)/2;
		   if (v[m]<x) l=m+1;
			  else r=m;
		  }
	m=(l+r)/2;
	if (v[m]<x) ++m;
	return m;
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	r=n;
	for (i=1; i<=n; ++i) scanf("%d",&v[i]);
	scanf("%d",&y);
	for (i=1; i<=y; ++i)
		{
		 scanf("%d%d",&t,&z);
		 if (t==0)
			{
			 x=z;
			 printf("%d\n",cb1(x));
			}
			else if (t==1)
					{
					 l=1;
					 r=n;
					 x=z;
					 printf("%d\n",cb2(x));
					}
					else
						{
						 l=1;
						 r=n;
						 x=z;
						 printf("%d",cb3(x));
						}
		}
	return 0;
}