탑

면접 대비

시간 제한1초메모리 제한1024 MB

요약

탑에서 K개 이상 이어진 같은 색 큐브 구간을 모두 지우는 과정을 더 이상 지울 구간이 없을 때까지 반복하고, 남은 큐브를 위에서 아래 순서로 출력합니다.

난이도: 보통10점 중 5점
유형: 스택, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

요나스는 색깔이 있는 큐브를 가지고 노는 것을 좋아한다. 그는 $N$ 개의 큐브를 차례로 쌓아 탑을 만들었다. 하지만 요나스는 이 탑이 마음에 들지 않는다. 같은 색 큐브가 길게 이어진 부분이 남지 않도록 탑을 다시 쌓고 싶어 한다.

이를 위해 요나스는 탑에서 길이가 $K$ 이상인 극대 단색 연속 구간을 모두 제거한다.

예를 들어 아래 탑과 $K = 3$ 을 보자. 요나스는 길이가 긴 초록색 큐브 구간을 제거한다. 그러면 아래의 새로운 탑이 된다.

제거할 구간이 여러 개 있으면 모두 동시에 제거한다.

탑을 다시 쌓으면 같은 색의 긴 구간이 또 생길 수 있다. 이때 요나스는 길이가 $K$ 이상인 단색 구간을 다시 모두 찾아 제거하고, 그 구간들을 뺀 채로 탑을 다시 쌓는다.

이 탑에서는 빨간색 큐브 구간의 길이가 $K = 3$ 이므로 요나스는 탑을 다시 쌓는다.

이 재배치 과정은 오래 반복될 수 있다. 모든 재배치가 끝난 후 탑이 어떤 모양인지 구하라.

입력

첫째 줄에 두 정수 $N$ 과 $K$ 가 주어진다. $N$ 은 탑의 높이이고, $K$ 는 제거 기준 길이이다.

다음 $N$ 개의 줄에 탑을 이루는 큐브의 색깔 번호가 정수로 주어진다. 첫째 줄은 맨 위 큐브의 색 $c_1$ 이다. 둘째 줄은 $c_1$ 큐브 아래에 있는 큐브의 색 $c_2$ 이다. $i$ 번째 줄은 $(i-1)$ 번째 큐브 아래에 있는 큐브의 색 $c_i$ 이다. $N$ 번째 줄은 맨 아래 큐브의 색 $c_N$ 이다.

출력

첫째 줄에 모든 재배치를 마친 뒤 탑의 높이 $N'$ 을 출력한다.

이어서 $N'$ 개의 줄에 $c'_1, c'_2, \dots, c'_{N'}$ 을 한 줄에 하나씩 출력한다. 탑의 맨 위부터 맨 아래까지 큐브의 색 번호이다.

제한

$1 \le N, K, c_i \le 1\,000\,000$

예제3

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