Description

RLE is a simple compression algorithm used to compress sequences that contain consecutive repetitions of the same character. By compressing a given sequence, we obtain its encoding. The idea is to use a counter to represent repetitions of a given character (e.g. $\texttt{aaaaa}$), indicating how many times it repeats. That is, we represent it using a triple consisting of a repetition marker, the repeated character, and an integer that represents the number of repetitions. For example, $\texttt{aaaaa}$ can be encoded as $\texttt{＃a5}$ (where $\texttt{＃}$ is the repetition marker).

We need some way to represent letters, the repetition marker, and the counter. Let the alphabet consist of $n$ characters, represented by integers from the set $\Sigma = \lbrace 0,1,\cdots,n-1 \rbrace$. The encoding of a character sequence over $\Sigma$ is also a character sequence over $\Sigma$. At any moment, the repetition marker is represented by a character from $\Sigma$, denoted by $e$. Initially, $e$ is $0$, but it may change during the encoding.

The encoding is interpreted as follows:

• Any character $a$ in the encoding, except for the repetition marker, represents itself.
• If the repetition marker $e$ occurs in the encoding, then the next two characters have special meanings:
  • If $e$ is followed by $ek$, it represents $k+1$ repetitions of $e$.
  • Otherwise, if $e$ is followed by $b0$ (where $b {=}\mathllap{/\,} e$), then $b$ becomes the repetition marker starting from that point.
  • Otherwise, if $e$ is followed by $bk$ (where $b {=}\mathllap{/\,} e$ and $k>0$), it represents $k+3$ repetitions of $b$.

Using the scheme above, we can encode any character sequence over $\Sigma$. For example, for $n=4$, the sequence $\texttt{1002222223333303020000}$ can be encoded as $\texttt{10010230320100302101}$. The first character $\texttt{1}$ in the encoding represents the plain character $\texttt{1}$. The next $\texttt{001}$ encodes $\texttt{00}$. Then $\texttt{023}$ represents $\texttt{222222}$, $\texttt{032}$ represents $\texttt{33333}$, and $\texttt{010}$ switches the repetition marker to $\texttt{1}$. After that, $\texttt{0302}$ represents itself, and finally $\texttt{101}$ encodes $\texttt{0000}$.

A sequence can be encoded in multiple ways, and the length of the encoding may vary. Given an already encoded sequence, your task is to find an encoding with the minimum number of characters.

Write a program that:

• Reads the size of the alphabet and the encoding of the sequence.
• Finds the shortest encoding of the sequence.
• Outputs the result.

Input Format

The first line contains an integer $n$, the size of the alphabet. The second line contains an integer $m$, the length of the encoding. The last line contains $m$ integers from $\lbrace 0,1,\cdots,n−1 \rbrace$, separated by single spaces, representing the encoding of the sequence.

Output Format

The first line should contain an integer $m'$, the minimum number of characters in an encoding that represents the given sequence. The last line of output should contain $m'$ integers from the set $\lbrace 0,1,\cdots,n−1 \rbrace$, separated by single spaces, giving an encoding of the sequence. If there are several shortest encodings, the program may output any one of them.

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

Hint

Constraints

For $100\%$ of the testdata, $2 \le n \le 10^5$, $1 \le m \le 2×10^6$.

Notes

The problem is from Baltic Olympiad in Informatics 2006, Day 2: RLE. Translated and整理 (pinyin: zhengli) by

Translated by ChatGPT 5