Multi-key Sorting

Consider a table made of rows and columns. The columns are numbered from 1 to C. For simplicity, every cell of the table holds a string of lowercase letters.

Table 1

The operation Sort(k) reorders the rows of a table by the values in column k, leaving the order of the columns unchanged. The sort is stable: rows that have equal values in column k keep their original relative order. For example, applying Sort(2) to Table 1 yields Table 2.

Table 2 (Table 1 after Sort(2))

We are interested in sequences of such operations applied successively to the same table. For example, applying Sort(2); Sort(1) to Table 1 yields Table 3.

Table 3 (Table 1 after Sort(2); Sort(1))

Two sequences of operations are equivalent if they have the same effect on every table. For example, Sort(2); Sort(2); Sort(1) is equivalent to Sort(2); Sort(1), but it is not equivalent to Sort(1); Sort(2), because their effects on Table 1 differ.

Given a sequence of sort operations, determine a shortest equivalent sequence. This shortest equivalent sequence can be shown to be unique, so you must output exactly that sequence.

The first line contains two integers C and N. C (1 ≤ C ≤ 1000000) is the number of columns and N (1 ≤ N ≤ 3000000) is the number of sort operations. The second line contains N integers k1 k2 … kN (1 ≤ ki ≤ C), describing the sequence Sort(k1); Sort(k2); …; Sort(kN).

On the first line, print one integer M, the length of the shortest sequence of sort operations equivalent to the input sequence. On the second line, print exactly M integers, separated by single spaces, describing that sequence.