#include<stdio.h>
long n,m,lo,hi,mid,last,a[100000],cer,x;
long cauta();
void cerinta();
int main()
{
   FILE*f=fopen("cautbin.in","r");
   fscanf(f,"%d",&n);
   int i=0;
   for(i;i<n;++i)
   fscanf(f,"%d",&a[i]);

   fscanf(f,"%d",&m);
   FILE*g=fopen("cautbin.out","w");
   for(;m;m--)
   {
	  fscanf(f,"%d%d",&cer,&x);
	  fprintf(g,"%d\n",cauta());
   }
   fclose(f);
   fclose(g);
   return 0;
}
long cauta()
{
	lo=0;
	hi=n;
	last=-2;
	while(lo<=hi)
	{
	   mid=lo+(hi-lo)/2;
	   cerinta();
	}
	return last+1;
}
void cerinta()
{
   switch(cer)
   {
	  case 0:
	  {
		 if(a[mid]<=x){if(a[mid]==x)last=mid;lo=mid+1;}
		 else hi=mid-1;
		 break;
	  }
	  case 1:
	  {
		 if(a[mid]<=x){last=mid;lo=mid+1;}
		 else hi=mid-1;
		 break;
	  }
	  case 2:
	  {
		 if(a[mid]>=x){last=mid;hi=mid-1;}
		 else lo=mid+1;
		 break;
	  }
   }
}