#include<stdio.h>
long n,m,v[100001],i,x,intr;

void read()
{
	scanf("%ld",&n);
	for(i=1;i<=n;++i)
		scanf("%ld",&v[i]);
	
}


long zero(long x)
{
	int med,st,dr,last=0;
	st=1;
	dr=n;
	while(st<=dr)
	{
		med=st+((dr-st)>>1);
		if (v[med]<=x)
		{ last=med;
		st=med+1;
		}
		else
			dr=med-1;
	}
	if (v[last]==x)
		return last;
	else
		return -1;
	}
	
	


long unu(long x)
{
		int med,st,dr,last=0;
	st=1;
	dr=n;
	while(st<=dr)
	{
		med=st+((dr-st)>>1);
		if (v[med]<=x)
		{ last=med;
		st=med+1;
		}
		else
			dr=med-1;
	}
	
		return last;
	}

long doi(long x)
{
		int med,st,dr,last=0;
	st=1;
	dr=n;
	while(st<=dr)
	{
		med=st+((dr-st)>>1);
		if (v[med]>=x)
		{ last=med;
		dr=med-1;
		}
		else
			st=med+1;
	}
	return last;
	}



int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	read();
	scanf("%ld",&m);
	for (i=1;i<=m;++i)
	{	scanf("%ld %ld",&intr,&x);
	   if (intr==0)
		   printf("%ld\n",zero(x));
	   else
		   if (intr==1)
			   printf("%ld\n",unu(x));
	   else
			    printf("%ld\n",doi(x));
		
	}
	
	
}