창구 조회 기록 보관함

문제

은행 창구 시스템은 고객의 업무 화면을 열 때마다 고객 번호로 기본 정보를 조회한다. 외부 저장소를 반복해서 조회하는 일을 줄이기 위해, 최근에 외부 저장소에서 가져온 정보를 임시 보관함에 넣어 둔다. 보관함에는 서로 다른 고객의 정보를 최대 K개까지 저장할 수 있다. 업무 시작 전 보관함은 비어 있다. 고객 번호가 요청되었을 때 그 고객의 정보가 보관함에 있으면 적중으로 처리한다. 이때 외부 저장소를 조회하지 않으며, 보관함 안에 있는 정보들의 순서도 바꾸지 않는다. 같은 고객의 요청이 여러 번 이어지더라도 적중한 정보가 새로 들어온 정보로 취급되지는 않는다. 고객의 정보가 보관함에 없으면 실패로 처리하고 외부 저장소에서 정보를 가져온다. 정보를 넣기 직전에 보관함에 이미 K개의 정보가 있다면, 현재 보관함에 남아 있는 정보 중 가장 먼저 들어온 정보 하나를 제거한다. 그런 다음 가져온 정보를 가장 나중 위치에 넣는다. 보관함에 빈자리가 있다면 제거 없이 정보를 넣는다. 한 번 제거된 고객의 정보가 이후 다시 요청되면, 그 요청 역시 실패다. 다시 가져온 정보는 과거에 들어왔던 시점과 관계없이 새로 들어온 것으로 취급한다. 모든 요청은 입력에 주어진 순서대로 하나씩 처리하며, 요청 사이에 자동 삭제나 다른 갱신 작업은 일어나지 않는다. 시스템 담당자는 보관함 크기에 따른 외부 저장소 조회 횟수를 확인하려 한다. 전체 요청을 처리한 뒤 실패 횟수와 적중 횟수를 구하고, 마지막에 보관함에 남은 고객 번호를 들어온 순서대로 출력한다. 요청은 하나 이상이고 보관함 크기도 하나 이상이므로, 처리가 끝난 보관함에는 항상 고객 정보가 하나 이상 남는다.

입력

첫째 줄에 보관함의 최대 정보 개수 K와 요청 개수 N이 공백으로 주어진다. 둘째 줄에 요청한 고객 번호 A_1, A_2, ..., A_N이 공백으로 주어진다.
모든 값은 정수이며 1 ≤ K ≤ 999, 1 ≤ N ≤ 50,000, 1 ≤ A_i ≤ 999다.

출력

첫째 줄에 실패 횟수와 적중 횟수를 이 순서로 공백으로 구분하여 출력한다. 둘째 줄에 마지막 보관함의 고객 번호를 가장 먼저 들어온 정보부터 가장 나중에 들어온 정보까지 공백으로 구분하여 출력한다.

2 7
1 2 1 3 2 4 1

5 2
4 1

1 4
7 7 8 8

2 2
8

출처: Devin.KR 자체 제작