题目描述

考虑一个包含行和列的表。列从 $1$ 到 $C$ 编号。为简单起见，表中的项目是由小写字母组成的字符串。

您将获得对此类表的 Sort($k$) 操作：Sort($k$) 按照列 $k$ 中的值的顺序对表的行进行排序（而列的顺序不会改变）。排序是稳定的，即在第 $k$ 列中具有相等值的行保持其原始顺序。例如，将 Sort($2$) 应用于表 $1$ 会产生表 $2$。
我们对此类排序操作的序列感兴趣。这些操作依次应用于同一个表。例如，应用序列 Sort($2$)；Sort($1$) 到表 $1$ 产生表 $3$。
如果两个排序操作序列对于任何表具有相同的效果，则它们被称为等效。例如，Sort($2$)；Sort($2$)；Sort($1$) 等效于 Sort($2$)；Sort($1$)。但是，它不等效于 Sort($1$)；Sort($2$)，因为对表 $1$ 的影响不同。

输入格式

第一行包含两个整数，$C$ 和 $N$。$C$ 是列数，$N$ 是排序操作数。第二行包含 $N$ 个整数，$k_i$。它定义了排序操作的顺序 Sort($k_1$)；$\cdots$； Sort($k_N$)。

输出格式

第一行包含一个整数 $M$，为输入的操作序列的最短等效排序操作序列的长度。第二行包含 $M$ 个整数，表示其最短操作序列。

4 6
1 2 1 2 3 3

3
1 2 3

提示

数据规模与约定

对于 $100 \%$ 的数据，$1 \leq C \leq 10^6$，$1 \leq N \leq 3×10^6$，$1 \leq k_i \leq C$。

题目说明

来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005 的 Multi-key Sorting。
由 @求学的企鹅 翻译整理。