#include <stdio.h>
#include <stdlib.h>


int V[100000];

int  binary1(int A,int B,int x)
{
  if (V[A]==x)
  {
  int y=V[A];
   while (V[A+1]==y)
   {
      A++;
   }
      return A;
  }
  else if (B==A) return -1;
  else
   {
      if (V[A+(B-A)/2]>x) return binary1(A,A+(B-A)/2,x);
      else return binary1(A+(B-A)/2,B,x);
   }
}


int binary2(int A,int B,int x)
{
  if ((V[A]<=x) && ((B==A) || (B==A+1)))
  {
    int y=V[A];
      while (V[A+1]==y)
   {
      A++;
   }
      return A;
  }
  else
  {
       if (V[A+(B-A)/2]>x) return binary2(A,A+(B-A)/2,x);
      else return binary2(A+(B-A)/2,B,x);
  }
}

int binary3(int A,int B,int x)
{
    if ((A==B) || (A+1==B))
    {
      if ((A==B) || (V[A]<x))
        {
        int y=V[B];
        while (V[B-1]==y) B--;
        return B;
        }
      else
        {
         int y=V[A];
        while (V[A-1]==y) A--;
        return A;
        }
    }
  else
  {
       if (V[A+(B-A)/2]>x) return binary3(A,A+(B-A)/2,x);
      else return binary3(A+(B-A)/2,B,x);
  }
}



int main()
{
  int n;

  FILE *f;
  FILE *g;

  f=fopen("cautbin.in","r");
  g=fopen("cautbin.out","w");

  fscanf(f,"%d",&n);
  V[0]=1999999999;
  V[n+1]=-1;
int i;
  for (i=1;i<=n;i++)
  {
    fscanf(f,"%d",&V[i]);
  }
 int x;
 int m;
 i==10000;
 fscanf (f,"%d",&m);
 while (m)
 {
 fscanf(f,"%d %d",&i,&x);

 if (i==0) fprintf(g,"%d\n",binary1(1,n,x));
 else if (i==1) fprintf(g,"%d\n",binary2(1,n,x));
 else if (i==2) fprintf(g,"%d\n",binary3(1,n,x));
 m--;
 }

fclose(g);
return 0;
}