let () = Scanf.scanf "%d\n" @@ fun n ->
  let as_ = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun a -> a in
  let acc = Array.make_matrix n (n + 2) 0 in
  for i = 0 to n - 1 do
    for j = 0 to i do
      acc.(j).(i + 2) <- as_.(i) + acc.(j).(i)
    done
  done;
  let i, j =
    Array.fold_left (Array.fold_left (List.fold_left (fun (i, j) (i', j') ->
      if acc.(i).(j) < acc.(i').(j') then (i', j') else (i, j)))) (0, 2) @@
    Array.init n @@ fun i ->
      Array.init (i + 1) @@ fun j ->
        if (i + j) mod 2 = 1 then [] else [(j, i + 2)] in
  Printf.printf "%d\n" acc.(i).(j);
  for k = n - 1 downto j - 1 do
    Printf.printf "%d\n" (k + 1)
  done;
  for k = j - 2 downto i do
    if (i + k) mod 2 = 1 then
      Printf.printf "%d\n" (k + 1)
  done;
  for k = i - 1 downto 0 do
    print_endline "1"
  done
