Program CautBin;

  var fi,fo:text;
      a:array[1..100000] of longint;
      n,m,i:1..100000;
      x,o:integer;

  Procedure Caut0(var key:integer);
   var st,dr,pivot:1..100000;

  begin
  st:=1; dr:=n;
  While st<=dr do begin
     pivot:=(st+dr) div 2;
      if a[pivot]<=key then st:=pivot+1
                       else dr:=pivot-1;

       end;

  pivot:=(st+dr) div 2;
  while (a[pivot]>key) do pivot:=pivot-1;
  if a[pivot]=key then key:=pivot
                  else key:=-1;



  end;


  Procedure Caut1(var key:integer);
   var st,dr,pivot:1..100000;

  begin
  st:=1; dr:=n;
  While st<dr do begin
     pivot:=(st+dr) div 2;
      if a[pivot]<=key then st:=pivot+1
                       else dr:=pivot;

       end;

  pivot:=(st+dr) div 2;
  While (a[pivot]>key) do pivot:=pivot-1;
  key:=pivot;
  end;


  Procedure Caut2(var key:integer);
   var st,dr,pivot:1..100000;

  begin
  st:=1; dr:=n;
  While st<dr do begin
     pivot:=(st+dr) div 2;
      If a[pivot]<key then st:=pivot+1
                      else dr:=pivot
                   end;
  pivot:=(st+dr) div 2;
  While a[pivot]<key do pivot:=pivot+1;
  key:=pivot;
  end;

  begin
   assign(fi,'cautbin.in');
   assign(fo,'cautbin.out');
   reset(fi);rewrite(fo);
   Readln(fi,n);
   For i:=1 to n do
   Read(fi,a[i]);
   readln(fi);
   Read(fi,m);
   For i:=1 to m do begin

         read(fi,o); read(fi,x);
         if o=0 then begin
                        Caut0(x);
                        if i<>1 then Writeln(fo);
                        Write(fo,x);
                        end;
          if o=1 then begin

                                      Caut1(x);
                                                Writeln(fo);
                                                Write(fo,x);
                                  end;
          if o=2 then begin
                                                Caut2(x);
                                                Writeln(fo);
                                                Write(fo,x);
                                                end;

                       end;

  close(fi);close(fo);
end.