다중 키 정렬

시간 제한2초메모리 제한128 MB

요약

안정 정렬로 이루어진 열 정렬 연산 수열이 주어질 때, 동일한 효과를 내는 가장 짧은 연산 수열을 구해야 합니다.

난이도: 보통10점 중 4점
유형: 배열, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

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

표 1

1번 열	2번 열	3번 열
apple	red	sweet
apple	green	sour
pear	green	sweet
banana	yellow	sweet
banana	brown	rotten

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

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

1번 열	2번 열	3번 열
banana	brown	rotten
apple	green	sour
pear	green	sweet
apple	red	sweet
banana	yellow	sweet

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

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

1번 열	2번 열	3번 열
apple	green	sour
apple	red	sweet
banana	brown	rotten
banana	yellow	sweet
pear	green	sweet

두 연산 열이 동치(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개의 정수를 공백 하나로 구분하여 출력한다.

예제6

예제 1
입력
```
4 6
1 2 1 2 3 3
```
예상 출력
```
3
1 2 3
```
예제 2
입력
```
1 2
1 1
```
예상 출력
```
1
1
```
예제 3
입력
```
2 2
1 2
```
예상 출력
```
2
1 2
```
예제 4
입력
```
2 2
2 1
```
예상 출력
```
2
2 1
```
예제 5
입력
```
2 3
2 2 1
```
예상 출력
```
2
2 1
```
예제 6
입력
```
5 1
5
```
예상 출력
```
1
5
```