#include<stdio.h>
long int n,m,v[100003],x;
FILE *in=fopen("cautbin.in","rt");
FILE *out=fopen("cautbin.out","wt");
long int zero()
{
  long int i,j,k;
  i=1;j=n;
  do
  {
    k=(i+j)/2;
    if(v[k]==x) return k;
    if(i>j) return -1;
		else
		{
			if(x>v[k]) i=k+1;
			else j=k-1;
		}
	}
	while(v[k]!=x && i<=j);
}
long int unu()
{
 int i,j,k,nr;
 i=1;j=n;
 do
 {
   k=(i+j)/2;
   if(v[k]<=x)
   {
     nr=k;i=k+1;
   }
   else j=k-1;
 }
 while(i<=j);
 return nr;

}
long int doi()
{
 int i,j,k,nr;
 i=1;j=n;
 do
 {
   k=(i+j)/2;
   if(v[k]>=x)
   {
     nr=k;j=k-1;
   }
   else i=k+1;
 }
 while(i<=j);
 return nr;

}
int main()
{
	long int i;
	int opt;
	fscanf(in,"%ld",&n);
	for(i=1;i<=n;i++) fscanf(in,"%ld",&v[i]);
	fscanf(in,"%ld",&m);
	for(i=1;i<=m;i++)
	{
		 fscanf(in,"%d",&opt);
		 fscanf(in,"%ld",&x);
		 if(opt==0) fprintf(out,"%ld\n",zero());
		 if(opt==1) fprintf(out,"%ld\n",unu());
		 if(opt==2) fprintf(out,"%ld\n",doi());
	}
	return 0;
}