종류가 바뀌면 봉인

문제

공장의 생산 라인에서는 완성된 제품이 정해진 순서대로 포장 지점에 도착한다. 각 제품에는 종류를 나타내는 정수 번호가 붙어 있다. 포장 담당자는 도착 순서를 바꾸거나 제품을 따로 보관할 수 없으며, 제품 하나를 처리한 뒤 다음 제품을 처리한다. 모든 상자는 제품을 최대 K개까지 담을 수 있고, 한 상자에는 같은 종류의 제품만 담을 수 있다. 작업을 시작할 때에는 열려 있는 상자가 없다. 열려 있는 상자가 없는 상태에서 제품이 도착하면 새 상자를 열고 그 제품을 넣는다. 열려 있는 상자의 제품과 같은 종류가 도착하면 그 상자에 제품을 넣는다. 제품을 넣은 결과 상자에 정확히 K개가 담기면 즉시 그 상자를 봉인한다. 봉인한 상자는 다시 열 수 없으며, 이때 다음 상자를 미리 열지는 않는다. 열려 있는 상자와 다른 종류의 제품이 도착하면, 먼저 열려 있는 상자를 현재 상태 그대로 봉인한다. 그 상자에 빈자리가 있어도 다른 종류의 제품으로 채울 수 없다. 이어서 새 상자를 열어 도착한 제품을 넣는다. 새 상자도 제품 수가 K개가 되면 즉시 봉인한다. 따라서 K가 1이면 모든 제품은 각각 별도의 상자에 담긴다. 마지막 제품까지 처리한 뒤에도 열려 있는 상자가 있으면 그 상자를 봉인하고 작업을 끝낸다. 이때 제품이 들어 있지 않은 상자를 새로 만들지는 않는다. 서로 떨어져 도착한 같은 종류의 제품도 이미 봉인한 상자를 공유할 수 없다. 공장은 사용한 상자 수와 낭비된 자리를 기록하려 한다. 상자 하나의 빈자리 수는 K에서 그 상자에 실제로 담긴 제품 수를 뺀 값이다. 생산 순서가 주어질 때, 봉인한 상자의 총개수와 모든 상자의 빈자리 수의 합을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 주어진다.
둘째 줄에 제품이 도착하는 순서대로 종류 번호 T1, T2, …, TN이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 100,000, 1 ≤ K ≤ 100,000, 1 ≤ Ti ≤ 9이다. 모든 입력값은 정수이다.

출력

봉인한 상자의 총개수와 모든 상자의 빈자리 수의 합을 공백으로 구분하여 한 줄에 출력한다.

9 3
2 2 2 2 5 5 2 2 2

4 3

5 1
4 4 7 4 7

5 0

4 6
8 8 8 8

1 2

출처: Devin.KR 자체 제작