#include<stdio.h>
long n,m,lo,hi,mid,last,a[100001],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-1;
    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;
      }
   }
}