다중 키 정렬

행과 열로 이루어진 표를 생각하자. 열에는 1번부터 C번까지 번호가 매겨져 있다. 편의를 위해 표의 각 칸에는 소문자 알파벳으로 이루어진 문자열이 들어 있다.

표 1

연산 Sort(k)는 열의 순서는 그대로 둔 채, 표의 행들을 k번 열의 값을 기준으로 정렬한다. 이 정렬은 안정 정렬(stable)이다. 즉, k번 열의 값이 같은 행들은 원래의 상대 순서를 그대로 유지한다. 예를 들어 표 1에 Sort(2)를 적용하면 표 2가 된다.

표 2 (표 1에 Sort(2)를 적용한 결과)

이러한 연산을 같은 표에 차례로 적용하는 연산 열을 생각한다. 예를 들어 표 1에 Sort(2); Sort(1)을 적용하면 표 3이 된다.

표 3 (표 1에 Sort(2); Sort(1)을 적용한 결과)

두 연산 열이 동치(equivalent)라는 것은, 어떤 표에 적용하더라도 결과가 항상 같다는 뜻이다. 예를 들어 Sort(2); Sort(2); Sort(1)은 Sort(2); Sort(1)과 동치이지만, Sort(1); Sort(2)와는 동치가 아니다. 표 1에 적용했을 때 결과가 다르기 때문이다.

정렬 연산 열이 주어질 때, 이와 동치인 가장 짧은 연산 열을 구하라. 이 가장 짧은 동치 연산 열은 유일함이 증명되어 있으므로, 바로 그 연산 열을 출력해야 한다.

첫째 줄에 두 정수 C와 N이 주어진다. C (1 ≤ C ≤ 1000000)는 열의 개수, N (1 ≤ N ≤ 3000000)은 정렬 연산의 개수이다. 둘째 줄에는 N개의 정수 k1 k2 … kN (1 ≤ ki ≤ C)이 주어지며, 이는 연산 열 Sort(k1); Sort(k2); …; Sort(kN)을 의미한다.

첫째 줄에 입력 연산 열과 동치인 가장 짧은 연산 열의 길이 M을 출력한다. 둘째 줄에 그 연산 열을 나타내는 정확히 M개의 정수를 공백 하나로 구분하여 출력한다.