open Stream
open Array
 
(** {1 Lemmas} *)
 
(** Alias for application operator. *)
let ($) f g = f g
(** Accessible to indexed_numbers only. *)
let current_index = ref (-1)
(** _ *)
(* NOTE: Fucking Ideone syntax highlighter does not understand
   empty comments. *)
let indexed_numbers : (int * int) Stream.t =
  Stream.from (fun index ->
    assert (index = !current_index + 1);
    try
      let result = Some (int_of_string $ read_line (), index) in
        current_index := index;
        result
    with End_of_file ->
      None
  )
(** array which holds last n items only *)
class type ['item_type] last_n_items_type =
  object
    (** (array#set i x; array#get j) = error if i > j && i < j - n *)
    method get : int -> 'item_type
    (** (array#set i x; array#get i) = x *)
    method set : int -> 'item_type -> unit
  end
class ['item_type] last_n_items (n : int) (initial_value : 'item_type) =
  object (self : 'item_type #last_n_items_type)
    val mutable impl = Array.make n initial_value
    method get i = impl.(i mod n)
    method set i (v : 'item_type) = impl.(i mod n) <- v
  end
(** _ *)
let times : int -> (unit -> unit) -> unit =
  fun n f ->
    for i = 0 to n do
      f ()
    done
(** The same as {val:min} but considers -1 as +infinity. *)
let unsigned_max : int -> int -> int =
  fun a b ->
    if a < b then b else a
 
(** {1 Proof} *)
let proof min_distance =
  let last_n_numbers = new last_n_items min_distance 0
  in
    (* Ignore data length *)
    ignore (next indexed_numbers);
    (* Populate last_n_numbers *)
    times min_distance (fun () ->
      let (number, index) = next indexed_numbers in
        last_n_numbers#set index number
    );
    (* Everybody do the flop! *)
    let rec max_prod first_max_number previous_max_prod =
      try
        let (number, index) = next indexed_numbers in
          let first_max_number =
            unsigned_max first_max_number (last_n_numbers#get index)
          in
            let previous_max_prod =
              unsigned_max previous_max_prod (first_max_number * number)
            in
              last_n_numbers#set index number;
              max_prod first_max_number previous_max_prod
      with Failure ->
        previous_max_prod
    and none = (-1)
    in
      (* Print result *)
      print_endline (string_of_int $ max_prod none none)
;;
proof 6;;

b3BlbiBTdHJlYW0Kb3BlbiBBcnJheQoKKCoqIHsxIExlbW1hc30gKikKCigqKiBBbGlhcyBmb3IgYXBwbGljYXRpb24gb3BlcmF0b3IuICopCmxldCAoJCkgZiBnID0gZiBnCigqKiBBY2Nlc3NpYmxlIHRvIGluZGV4ZWRfbnVtYmVycyBvbmx5LiAqKQpsZXQgY3VycmVudF9pbmRleCA9IHJlZiAoLTEpCigqKiBfICopCigqIE5PVEU6IEZ1Y2tpbmcgSWRlb25lIHN5bnRheCBoaWdobGlnaHRlciBkb2VzIG5vdCB1bmRlcnN0YW5kCiAgIGVtcHR5IGNvbW1lbnRzLiAqKQpsZXQgaW5kZXhlZF9udW1iZXJzIDogKGludCAqIGludCkgU3RyZWFtLnQgPQogIFN0cmVhbS5mcm9tIChmdW4gaW5kZXggLT4KICAgIGFzc2VydCAoaW5kZXggPSAhY3VycmVudF9pbmRleCArIDEpOwogICAgdHJ5CiAgICAgIGxldCByZXN1bHQgPSBTb21lIChpbnRfb2Zfc3RyaW5nICQgcmVhZF9saW5lICgpLCBpbmRleCkgaW4KICAgICAgICBjdXJyZW50X2luZGV4IDo9IGluZGV4OwogICAgICAgIHJlc3VsdAogICAgd2l0aCBFbmRfb2ZfZmlsZSAtPgogICAgICBOb25lCiAgKQooKiogYXJyYXkgd2hpY2ggaG9sZHMgbGFzdCBuIGl0ZW1zIG9ubHkgKikKY2xhc3MgdHlwZSBbJ2l0ZW1fdHlwZV0gbGFzdF9uX2l0ZW1zX3R5cGUgPQogIG9iamVjdAogICAgKCoqIChhcnJheSNzZXQgaSB4OyBhcnJheSNnZXQgaikgPSBlcnJvciBpZiBpID4gaiAmJiBpIDwgaiAtIG4gKikKICAgIG1ldGhvZCBnZXQgOiBpbnQgLT4gJ2l0ZW1fdHlwZQogICAgKCoqIChhcnJheSNzZXQgaSB4OyBhcnJheSNnZXQgaSkgPSB4ICopCiAgICBtZXRob2Qgc2V0IDogaW50IC0+ICdpdGVtX3R5cGUgLT4gdW5pdAogIGVuZApjbGFzcyBbJ2l0ZW1fdHlwZV0gbGFzdF9uX2l0ZW1zIChuIDogaW50KSAoaW5pdGlhbF92YWx1ZSA6ICdpdGVtX3R5cGUpID0KICBvYmplY3QgKHNlbGYgOiAnaXRlbV90eXBlICNsYXN0X25faXRlbXNfdHlwZSkKICAgIHZhbCBtdXRhYmxlIGltcGwgPSBBcnJheS5tYWtlIG4gaW5pdGlhbF92YWx1ZQogICAgbWV0aG9kIGdldCBpID0gaW1wbC4oaSBtb2QgbikKICAgIG1ldGhvZCBzZXQgaSAodiA6ICdpdGVtX3R5cGUpID0gaW1wbC4oaSBtb2QgbikgPC0gdgogIGVuZAooKiogXyAqKQpsZXQgdGltZXMgOiBpbnQgLT4gKHVuaXQgLT4gdW5pdCkgLT4gdW5pdCA9CiAgZnVuIG4gZiAtPgogICAgZm9yIGkgPSAwIHRvIG4gZG8KICAgICAgZiAoKQogICAgZG9uZQooKiogVGhlIHNhbWUgYXMge3ZhbDptaW59IGJ1dCBjb25zaWRlcnMgLTEgYXMgK2luZmluaXR5LiAqKQpsZXQgdW5zaWduZWRfbWF4IDogaW50IC0+IGludCAtPiBpbnQgPQogIGZ1biBhIGIgLT4KICAgIGlmIGEgPCBiIHRoZW4gYiBlbHNlIGEKCigqKiB7MSBQcm9vZn0gKikKbGV0IHByb29mIG1pbl9kaXN0YW5jZSA9CiAgbGV0IGxhc3Rfbl9udW1iZXJzID0gbmV3IGxhc3Rfbl9pdGVtcyBtaW5fZGlzdGFuY2UgMAogIGluCiAgICAoKiBJZ25vcmUgZGF0YSBsZW5ndGggKikKICAgIGlnbm9yZSAobmV4dCBpbmRleGVkX251bWJlcnMpOwogICAgKCogUG9wdWxhdGUgbGFzdF9uX251bWJlcnMgKikKICAgIHRpbWVzIG1pbl9kaXN0YW5jZSAoZnVuICgpIC0+CiAgICAgIGxldCAobnVtYmVyLCBpbmRleCkgPSBuZXh0IGluZGV4ZWRfbnVtYmVycyBpbgogICAgICAgIGxhc3Rfbl9udW1iZXJzI3NldCBpbmRleCBudW1iZXIKICAgICk7CiAgICAoKiBFdmVyeWJvZHkgZG8gdGhlIGZsb3AhICopCiAgICBsZXQgcmVjIG1heF9wcm9kIGZpcnN0X21heF9udW1iZXIgcHJldmlvdXNfbWF4X3Byb2QgPQogICAgICB0cnkKICAgICAgICBsZXQgKG51bWJlciwgaW5kZXgpID0gbmV4dCBpbmRleGVkX251bWJlcnMgaW4KICAgICAgICAgIGxldCBmaXJzdF9tYXhfbnVtYmVyID0KICAgICAgICAgICAgdW5zaWduZWRfbWF4IGZpcnN0X21heF9udW1iZXIgKGxhc3Rfbl9udW1iZXJzI2dldCBpbmRleCkKICAgICAgICAgIGluCiAgICAgICAgICAgIGxldCBwcmV2aW91c19tYXhfcHJvZCA9CiAgICAgICAgICAgICAgdW5zaWduZWRfbWF4IHByZXZpb3VzX21heF9wcm9kIChmaXJzdF9tYXhfbnVtYmVyICogbnVtYmVyKQogICAgICAgICAgICBpbgogICAgICAgICAgICAgIGxhc3Rfbl9udW1iZXJzI3NldCBpbmRleCBudW1iZXI7CiAgICAgICAgICAgICAgbWF4X3Byb2QgZmlyc3RfbWF4X251bWJlciBwcmV2aW91c19tYXhfcHJvZAogICAgICB3aXRoIEZhaWx1cmUgLT4KICAgICAgICBwcmV2aW91c19tYXhfcHJvZAogICAgYW5kIG5vbmUgPSAoLTEpCiAgICBpbgogICAgICAoKiBQcmludCByZXN1bHQgKikKICAgICAgcHJpbnRfZW5kbGluZSAoc3RyaW5nX29mX2ludCAkIG1heF9wcm9kIG5vbmUgbm9uZSkKOzsKcHJvb2YgNjs7

OQoxMgoyMgoyMQo1CjQKOQo0NQoxMAoxMg==

9
12
22
21
5
4
9
45
10
12