type puzzle = { board : int array; space : int; md : int; cost : int }
type state = { puzzle : puzzle; estimated : int }

module MakeBinaryHeap (M : sig type t val compare : t -> t -> int end) = struct

  type t = { node : M.t array; mutable size : int }

  let make n (init : M.t) = { node = Array.make n init; size = 0 }

  let empty_p t = if t.size = 0 then true else false

  let pop t =
    if t.size <= 0 then failwith "out of size" else
    let rec max_heapify i =
      let l = 2*i in
      let r = 2*i + 1 in
      let m = if l <= t.size && M.compare t.node.(l) t.node.(i) > 0 then l else i in
      let m = if r <= t.size && M.compare t.node.(r) t.node.(m) > 0 then r else m in
      if m = i then ()
      else begin
        let tmp = t.node.(i) in
        t.node.(i) <- t.node.(m);
        t.node.(m) <- tmp;
        max_heapify m
      end in
    let ret = t.node.(1) in
    t.node.(1) <- t.node.(t.size);
    t.size <- t.size - 1;
    max_heapify 1;
    ret

  let push x t =
    let parent i = int_of_float (floor (float_of_int i) /. 2.) in
    let rec doit i =
      let p = parent i in
      if i <= 1 || M.compare t.node.(p) t.node.(i) >= 0 then ()
      else begin
        let tmp = t.node.(i) in
        t.node.(i) <- t.node.(p);
        t.node.(p) <- tmp;
        doit p
      end in
    t.size <- t.size + 1;
    t.node.(t.size) <- x;
    doit t.size

end

module H = MakeBinaryHeap(struct type t = state let compare x y = y.estimated - x.estimated end)

let (n1, n2) = (4, 16)
let n_limit = 100
let mdt = Array.make_matrix n2 n2 0
let dx = [| 0; -1; 0; 1 |]
let dy = [| 1; 0; -1; 0 |]

let astar board space =
  let (_, md) =
    Array.fold_left (fun (i, sum) e ->
      (i + 1, if e = n2 then sum else sum + mdt.(i).(e-1)))
      (0, 0) board in
  let pzl = { board; space; md; cost = 0 } in
  let initial = { puzzle = pzl; estimated = pzl.md } in
  let que = H.make 1000 { puzzle = { board = [||]; space = 0; md = 0; cost = 0 }; estimated = 0 } in
  H.push initial que;
  let tbl = Hashtbl.create ~random:true 1000 in
  let rec doit () =
    if H.empty_p que then assert false else
    let st = H.pop que in
    let { board = b; space = s; md = m; cost = c } = st.puzzle in
    let u = { board = Array.copy b; space = s; md = m; cost = c } in
    if u.md == 0 then u.cost
    else begin
      Hashtbl.add tbl u true;
      let (sx, sy) = (u.space / n1, u.space mod n1) in
      let rec aux r =
        if r = 4 then () else
        let (tx, ty) = (sx + dx.(r), sy + dy.(r)) in
        if tx < 0 || ty < 0 || tx >= n1 || ty >= n1 then aux (r + 1)
        else begin
          let { board; md; cost } = u in
          let board = Array.copy board in
          let (a, b) = (tx * n1 + ty, sx * n1 + sy) in
          let md = md - mdt.(a).(board.(a) - 1) in
          let md = md + mdt.(b).(board.(a) - 1) in
          let t = board.(a) in
          board.(a) <- board.(b);
          board.(b) <- t;
          let space = a in
          if not (Hashtbl.mem tbl { board; space; md; cost }) then begin
            let v = { board; space = a; md; cost = cost + 1 } in
            H.push { puzzle = v; estimated = v.cost + v.md } que;
          end;
          aux (r + 1)
        end in
      aux 0;
      doit ()
    end in
  doit ()

let () =
  for i = 0 to n2 - 1 do
    for j = 0 to n2 - 1 do
      mdt.(i).(j) <- abs (i / n1 - j / n1) + abs (i mod n1 - j mod n1)
    done
  done;
  let board = Array.make n2 0 in
  let rec doit i space =
    if i = n2 then space
    else begin
      let x = Scanf.scanf "%d " (fun i -> i) in
      let (x, space) = if x = 0 then (n2, i) else (x, space) in
      board.(i) <- x;
      doit (i + 1) space
    end in
  doit 0 0 |> astar board |> Printf.printf "%d\n"