题目描述

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'$ 个整数，以单个空格分隔：该序列的编码。如果存在几个最短的序列，则程序应输出其中的任何一个。

4
20
1 0 0 1 0 2 3 0 3 2 0 1 0 0 3 0 2 1 0 1

19
1 0 1 0 0 0 1 2 3 1 3 2 0 3 0 2 1 0 1

14
15
10 10 10 0 10 0 10 10 13 10 10 13 10 10 13

9
0 10 13 0 10 13 0 10 10

提示

数据规模与约定

对于 $100 \%$ 的数据，$2 \le n \le 10^5$，$1 \le m \le 2×10^6$。

题目说明

来源于 Baltic Olympiad in Informatics 2006 的 Day 2:RLE。
由