P7641 [BalticOI 2006] RLE COMPRESSION (Day 2)

RLE 是一种简单的压缩算法，用于压缩包含相同字符后续重复的序列。 通过压缩特定的序列，我们获得其编码。这个想法是用一个计数器表示给定字符（例如 $\texttt{aaaaa}$）的重复，以表示有多少次重复。即，我们用包含重复标记，重复字符和代表重复次数的整数的三元组来表示它。 例如，$\texttt{aaaaa}$ 可以编码为 $\texttt{＃a5}$ （其中 $\texttt{＃}$ 表示重复标记）。 我们需要以某种方式表示字母，重复标记和计数器。让字母由 $n$ 个字符组成，这些字符由集合 $\Sigma= \lbrace 0,1, \cdots ,n-1 \rbrace$ 中的整数表示。来自 $\Sigma$ 的字符序列的编码也是来自 $\Sigma$ 的字符序列。 在任何时候，重复标记都由 $\Sigma$ 中的字符表示，用 $e$ 表示。最初 $e$ 为 $0$，但在编码过程中可能会改变。 该编码解释如下： - 除重复标记外，编码中的任何字符 $a$ 都表示自身； - 如果编码中出现重复标记 $e$，则以下两个字符具有特殊含义： $\circ$ 如果 $e$ 后面跟着 $ek$，则表示 $e$ 的 $k+1$ 个重复， $\circ$ 否则，如果 $e$ 后跟 $b0$（其中 $b {=}\mathllap{/\,} e$），则 $b$ 将是从该点开始的重复标记， $\circ$ 否则，如果 $e$ 后面跟随 $bk$（其中 $b {=}\mathllap{/\,} e$ 并且 $k>0$），则它表示 $b$ 的 $k+3$ 个重复。 使用上述方案，我们可以从 $\Sigma$ 编码任何字符序列。例如，对于 $n=4$，序列 $\texttt{1002222223333303020000}$ 可以编码为 $\texttt{10010230320100302101}$。编码 $\texttt{1}$ 的第一个字符表示简单 $\texttt{1}$。接下来的 $\texttt{001}$ 编码为 $\texttt{00}$。然后，$\texttt{023}$ 表示 $\texttt{222222}$，$\texttt{032}$ 表示 $\texttt{33333}$，而 $\texttt{010}$ 将重复标记切换为 $\texttt{1}$，然后 $\texttt{0302}$ 代表自己，最后 $\texttt{101}$ 编码 $\texttt{0000}$。 序列可以以多种方式编码，并且编码长度可以变化。给定一个已经编码的序列，您的任务是查找字符数最少的编码。 编写一个程序，该程序： - 读取字母的大小和序列的编码。 - 查找该序列的最短编码。 - 写出结果。

第一行包含一个整数 $n$：字母的大小。第二行包含一个整数 $m$：编码的长度。最后一行包含 $\lbrace 0,1, \cdots ,n−1 \rbrace$ 中的 $m$ 个整数，这些整数之间用单个空格分隔，表示序列的编码。

第一行应包含一个整数 $m'$：代表给定序列的编码中最少的字符数。输出的最后一行应包含集合 $\lbrace 0,1, \cdots ,n−1 \rbrace $中的 $m'$ 个整数，以单个空格分隔：该序列的编码。如果存在几个最短的序列，则程序应输出其中的任何一个。

#### 数据规模与约定 对于 $100 \%$ 的数据，$2 \le n \le 10^5$，$1 \le m \le 2×10^6$。 #### 题目说明 来源于 [Baltic Olympiad in Informatics 2006](https://www.cs.helsinki.fi/group/boi2006/) 的 [Day 2:RLE](https://www.cs.helsinki.fi/group/boi2006/tasks/rle.pdf)。 由 @[求学的企鹅](/user/271784) 翻译整理。 Special Judge 感谢 Jakub Pawlewicz 和 @[AzzyZhe](/user/274209)。