(*
 * $Id: heapsort.ocaml,v 1.9 2001/05/08 02:46:59 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 * with help from Markus Mottl
 *)

let im = 139968
let ia =   3877
let ic =  29573
let last = ref 42

let gen_random max =
  last := (!last * ia + ic) mod im;
  max *. float_of_int !last /. float_of_int im

let heapsort n ra =
  let l = ref ((n lsr 1) + 1)
  and rra = ref 0.0
  and i = ref 0
  and j = ref 0
  and ir = ref n in
  try
    while true do
      if !l > 1 then begin
        decr l;
        rra := ra.(!l)
      end
      else begin
        rra := ra.(!ir);
        ra.(!ir) <- ra.(1);
        decr ir;
        if !ir = 1 then begin
          ra.(1) <- !rra;
          raise Exit
        end
      end;
      i := !l;
      j := !l lsl 1;
      while !j <= !ir do
        if !j < !ir && ra.(!j) < ra.(!j+1) then incr j;
        if !rra < ra.(!j) then begin
          ra.(!i) <- ra.(!j);
          i := !j;
          j := !j + !i
        end
        else j := !ir + 1;
      done;
      ra.(!i) <- !rra;
    done
  with Exit -> ()

let _ =
  let n =
    try int_of_string Sys.argv.(1)
    with Invalid_argument _ -> 1 in
  let ary = Array.make (n + 1) 0.0 in
  for i = 1 to n do
     ary.(i) <- gen_random 1.0
  done;
  heapsort n ary;
  Printf.printf "%.10f\n" ary.(n)