스마트 홈의 설정 보관함

문제

스마트 홈의 중앙 제어기는 기기에 명령을 보낼 때 해당 기기의 설정을 확인한다. 설정 원본은 별도의 저장 장치에 있으며, 자주 사용하는 설정을 빠르게 찾기 위해 중앙 제어기에 작은 캐시를 둔다. 각 기기의 설정은 같은 크기의 공간 하나를 차지한다. 캐시에 저장할 수 있는 설정의 최대 개수는 C개이며, 처음에는 캐시가 비어 있다. 명령 요청에는 기기 번호 하나가 들어 있다. 요청한 기기의 설정이 이미 캐시에 있으면 적중이다. 적중한 경우에는 저장 장치를 읽지 않으며, 캐시에 들어 있는 설정의 순서도 바꾸지 않는다. 같은 기기가 연속해서 요청되더라도 이 규칙을 그대로 적용한다. 요청한 기기의 설정이 캐시에 없으면 누락이다. 누락이 발생할 때마다 저장 장치에서 설정을 한 번 읽는다. C가 양수이면 읽은 설정을 캐시에 넣는다. 이때 캐시가 이미 C개의 설정을 보관하고 있다면, 현재 캐시에 남아 있는 설정 중 가장 먼저 들어온 설정을 하나 제거한 다음 새 설정을 넣는다. 빈자리가 있다면 제거 없이 넣는다. 제거된 설정이 나중에 다시 요청되면 다시 저장 장치를 읽고, 새로 들어온 설정으로 취급한다. C가 0이면 설정을 보관할 공간이 없다. 이 경우 모든 요청마다 저장 장치를 한 번씩 읽으며, 요청을 처리한 뒤에도 캐시는 항상 비어 있다. 기기 번호는 설정을 구별하는 식별자일 뿐이며, 번호가 작거나 큰 것은 제거 순서와 관계없다. 중앙 제어기는 모든 요청을 입력된 순서대로 정확히 한 번씩 처리한다. 처리 도중 캐시 용량이 달라지거나 요청 이외의 이유로 설정이 추가 또는 삭제되는 일은 없다. 전체 요청을 처리했을 때 저장 장치를 읽은 횟수와 캐시에 남은 기기 번호를 구한다. 남은 번호는 현재 보관 중인 설정이 캐시에 들어온 순서대로, 가장 오래된 것부터 출력한다.

입력

첫째 줄에 요청 수 N과 캐시 용량 C가 주어진다. 둘째 줄에 요청 순서대로 기기 번호 D_1, D_2, ..., D_N이 주어진다. 모든 입력값은 정수이며 1≤N≤60,000, 0≤C≤10,000, 1≤D_i≤9,999이다.

출력

첫째 줄에 저장 장치를 읽은 횟수를 출력한다. 둘째 줄에 캐시에 남은 기기 번호를 가장 먼저 들어온 것부터 공백으로 구분하여 출력한다. 캐시가 비어 있으면 둘째 줄에 -1만 출력한다.

7 2
4 8 4 9 8 4 9

4
9 4

4 0
3 3 8 3

4
-1

5 4
7 7 2 7 2

2
7 2

출처: Devin.KR 자체 제작