#include<stdio.h>

int v[1000010],n,m,i,ls,ld,mj,a,x,ok;


int main ()
{


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

fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
  fscanf(f,"%d",&v[i]);

fscanf (f,"%d",&m);
for (i=1;i<=m;i++)
{


fscanf(f,"%d %d",&a,&x);
if (a==0)
    {
     ls=1;
     ld=n;
     mj=ls+(ld-ls)/2+1;

     ok=0;

     while (ls<ld&&!ok)
     {
      if (v[mj]<x) {ls=mj+1;
		    mj=ls+(ld-ls)/2;}
      if (v[mj]>x) {ld=mj-1;
		    mj=ls+(ld-ls)/2;}

      if (v[mj]==x) ok=1;
     }
     if (ok==0) fprintf(g,"-1\n");
	else fprintf(g,"%d\n",mj);
    }
if (a==1)
    {
     ls=1;
     ld=n;
     mj=ls+(ld-ls)/2;

     while (ls<ld)
     {
      if (v[mj]<=x) {ls=mj+1;
		    mj=ls+(ld-ls)/2;}
      if (v[mj]>x) {ld=mj-1;
		    mj=ls+(ld-ls)/2;}

     }
     if (x=v[mj])
	   fprintf(g,"%d\n",mj);
	 else fprintf(g,"%d\n",mj-1);
    }
if (a==2)
    {
     ls=1;
     ld=n;
     mj=ls+(ld-ls)/2;

     while (ls<ld)
     {
      if (v[mj]<=x) {ls=mj+1;
		    mj=ls+(ld-ls)/2;}
      if (v[mj]>x) {ld=mj-1;
		    mj=ls+(ld-ls)/2;}

     }
     if (v[mj-1]==x)fprintf(g,"%d\n",mj-1);
	else fprintf(g,"%d\n",mj);
    }

}
fclose(f);
fclose(g);
return 0;
}