P7686 [CEOI 2005] Multi-key Sorting

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.

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$).

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.

#### 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 @[求学的企鹅](/user/271784). Translated by ChatGPT 5