Description

Consider a table with rows and columns. The columns are numbered from $1$ to $C$. For simplicity, the entries in the table are strings consisting of lowercase letters.

You are given Sort($k$) operations on such tables: Sort($k$) sorts the rows of the table by the values in column $k$ (the order of columns does not change). The sorting is stable, meaning that rows with equal values in column $k$ keep their original relative order. For example, applying Sort($2$) to table $1$ produces table $2$.
We are interested in sequences of such sorting operations. These operations are applied one after another to the same table. For example, applying the sequence Sort($2$); Sort($1$) to table $1$ produces table $3$.
Two sequences of sorting operations are called equivalent if they have the same effect on any table. For example, Sort($2$); Sort($2$); Sort($1$) is equivalent to Sort($2$); Sort($1$). However, it is not equivalent to Sort($1$); Sort($2$), because the effect on table $1$ is different.

Input Format

The first line contains two integers, $C$ and $N$. $C$ is the number of columns, and $N$ is the number of sorting operations. The second line contains $N$ integers, $k_i$. It defines the sequence of sorting operations Sort($k_1$); $\cdots$; Sort($k_N$).

Output Format

The first line contains an integer $M$, the length of the shortest sorting-operation sequence that is equivalent to the given sequence. The second line contains $M$ integers, describing this shortest sequence.

4 6
1 2 1 2 3 3

3
1 2 3

Hint

Constraints

For $100\%$ of the data, $1 \leq C \leq 10^6$, $1 \leq N \leq 3×10^6$, $1 \leq k_i \leq C$.

Problem Notes

From Multi-key Sorting, CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005.
Translated and organized by @求学的企鹅.

Translated by ChatGPT 5