아이스크림 기계

진정한 아이슬란드인인 Arnar는 아이스크림을 무척 좋아하며, 오늘은 이 맛있는 간식을 사러 가기에 더없이 좋은 날씨다. 그는 눈보라를 뚫고 자신이 가장 좋아하는 아이스크림 가게로 향한다. 도착한 그는 앞에 늘어선 줄이 평소와 달리 짧은 것을 보고 놀란다. 주문을 기다리는 사람 중 자신이 고작 $n$번째이기 때문이다!

Arnar는 이 아이스크림 가게를 잘 안다. 이곳에서는 서로 다른 $m$가지 맛을 제공하며, 아이스크림 기계가 $k$대 있다. 하지만 각 기계는 한 번에 한 가지 맛만 제공할 수 있고, 다른 맛을 채우기 전에는 기계를 세척해야 한다. 기계를 세척하는 데 시간이 좀 걸리고 Arnar는 서두르고 있으므로, 고객에게 제공할 새로운 맛이 필요할 때마다 세척할 최적의 기계를 가게 운영자가 결정하도록 도와서 기계를 세척해야 하는 총횟수를 최소화할 수 있을지 궁금해한다.

다행히 아이슬란드는 작은 곳이라 Arnar는 줄에 선 모든 사람과 그들이 원하는 아이스크림 맛을 알고 있다. 가게는 새치기 금지 방침을 엄격히 시행하므로, 고객들이 도착한 순서대로 응대한다. Arnar 자신을 포함하여 줄에 선 모든 사람에게 아이스크림을 제공하기 위해 아이스크림 기계를 세척해야 하는 최소 횟수를 구하도록 Arnar를 도와줄 수 있는가?

처음에는 모든 아이스크림 기계가 비어 있으며, 첫 번째 맛을 채우기 전에 세척해야 한다. 아이스크림 기계에 특정 맛을 채우고 나면, 그 기계를 세척하여 다른 맛을 채울 때까지 해당 맛을 원하는 고객을 몇 명이든 응대하는 데 사용할 수 있다. 전혀 사용하지 않는 기계는 세척할 필요가 없다.

채점

그룹 | 점수 | 제한 조건

1      |   7    |  $N \leq 1\,000$,          $M \leq 10$, $K = 1$

2      |   12   |  $N \leq 1\,000$,          $M \leq 10$, $K \leq 2$

3      |   22   |  $N \leq 1\,000$,          $M \leq 10$, $K \leq 5$

4      |   11   |  $N \leq 1\,000$,         $M \leq 200$, $K \leq 100$

5      |   14   |  $N \leq 2 \cdot 10^5$, $M \leq 500$, $K \leq 100$

6      |   13   |  $N \leq 2 \cdot 10^5$, $M \leq 2 \cdot 10^5$, $K \leq 100$

7      |   21   |  $N \leq 2 \cdot 10^5$, $M \leq 2 \cdot 10^5$, $K \leq 2 \cdot 10^5$

입력은 다음으로 구성된다.

• 정수 $n$, $m$, $k$ 세 개가 주어지는 한 줄. 이들은 각각 줄에서 기다리는 고객의 수, 제공되는 맛의 수, 아이스크림 기계의 수를 나타낸다.

• $n$개의 줄. 이 중 $i$번째 줄에는 정수 $c_i$가 주어지며, $1 \leq c_i \leq m$이다. 이는 줄의 $i$번째 고객이 원하는 맛을 나타낸다.

$n$명의 고객 모두에게 아이스크림을 제공하기 위해 아이스크림 기계를 세척해야 하는 최소 총횟수를 출력한다.