주차장 허가 정보 보관함

문제

주차장 입구의 시스템은 차량이 도착할 때마다 해당 차량의 출입 허가 정보를 확인한다. 차량은 서로 다른 양의 정수 번호로 구분한다. 모든 차량의 허가 정보는 중앙 저장소에 있지만, 자주 사용하는 정보를 빠르게 확인하기 위해 입구 장치에도 최대 K개의 정보를 보관한다. 입구 장치의 보관함은 처음에 비어 있다. 차량의 도착 기록은 발생한 순서대로 주어진다. 도착한 차량의 정보가 이미 보관함에 있으면 그 정보를 바로 사용한다. 이때 중앙 저장소를 조회하지 않으며, 보관함 안에서 정보의 순서도 바꾸지 않는다. 같은 차량이 연속으로 도착해도 매번 이 규칙을 적용한다. 도착한 차량의 정보가 보관함에 없으면 중앙 저장소를 정확히 한 번 조회한다. 그 뒤 해당 정보를 보관함에 새로 넣는다. 넣기 직전에 보관함에 K개의 정보가 있다면, 현재 보관된 정보 중 가장 먼저 들어온 정보를 하나 제거한 다음 새 정보를 넣는다. 제거되었던 차량의 정보가 나중에 다시 들어오면 그 시점을 새로운 보관 시작 시점으로 취급한다. 입구 장치는 조회 비용과 종료 시점의 보관 상태를 함께 점검하려 한다. 모든 도착 기록을 처리했을 때 중앙 저장소를 조회한 총횟수와 마지막 보관함의 내용을 구한다. 보관함의 내용은 현재 남아 있는 정보가 들어온 순서대로, 가장 오래된 것부터 출력해야 한다. 차량 번호의 크기는 제거 순서에 영향을 주지 않는다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. N은 도착 기록의 수이며 1≤N≤60,000이다. 보관 용량 K는 1≤K≤N이다.
둘째 줄에 도착 순서대로 차량 번호 N개가 공백으로 구분되어 주어진다. 각 차량 번호는 1 이상 60,000 이하의 정수이다.

출력

첫째 줄에 중앙 저장소 조회 횟수를 출력한다. 둘째 줄에 마지막 보관함에 남은 차량 번호를 가장 먼저 들어온 것부터 공백으로 구분하여 출력한다. N과 K가 양수이므로 마지막 보관함은 항상 비어 있지 않다.

7 3
1 2 1 3 4 2 1

5
3 4 1

4 1
5 5 5 5

1
5

출처: Devin.KR 자체 제작