题目描述

题目译自 XV OI Olimpiada Informatyczna – I etap Klocki

Bajtazar 小时候酷爱玩积木。他的玩法是将积木堆成 $n$ 列，每列高度随机选择，然后进行整理。他会选定一个数字 $k$，试图以最少的操作次数整理积木，使某 $k$ 列连续的积木高度相同。每次操作包括：

• 在任一列顶端放置一块积木（Bajtazar 有大量备用积木，此操作始终可行）。
• 从任一列顶端移除一块积木。

Bajtazar 总不确定自己的方案是否最优，请求你编写程序帮助他解决这一问题。

编写程序：

• 从标准输入读取 $k$ 和初始积木布局描述。
• 确定需要最少操作次数的解决方案。
• 将结果输出到标准输出。

输入格式

第一行包含两个整数 $n, k$ $(1 \leq k \leq n \leq 100000)$，用单空格分隔。接下来的 $n$ 行描述初始积木列高度，第 $i+1$ 行包含一个整数 $h_i$ $(0 \leq h_i \leq 1000000)$，表示第 $i$ 列积木的高度，即该列包含的积木块数。

输出格式

输出最优解决方案，即满足以下条件的积木布局：

• 包含 $k$ 列连续的积木高度相同。
• 可通过最少操作次数从初始布局获得。

输出包含 $n+1$ 行，每行一个整数。第一行输出达成目标布局所需的最少操作次数。第 $i+1$ $(1 \leq i \leq n)$ 行输出 $h_i'$，表示第 $i$ 列的最终高度。若存在多种方案，输出任意一种。

5 3
3
9
2
3
1

2
3
9
2
2
2