Ice Cream Machines

Interview

Time limit2sMemory limit1024 MB

Summary

Given a queue of flavour requests and k machines, find the fewest machine cleanings needed to serve every customer in order.

Level: Medium5 of 10
Topics: Greedy, Simulation, Array
Solved: No attempts yet

Problem

Arnar is a true Icelander and loves ice cream. Today a blizzard is blowing, but he heads to his favourite ice cream store anyway. When he arrives, the queue is unusually short. He is the $n$ th person waiting to order. The store offers $m$ flavours and has $k$ ice cream machines. Each machine can serve only one flavour at a time, and a machine must be cleaned before it is loaded with a different flavour. Cleaning takes time, and Arnar is in a hurry. Each time a new flavour is needed for a customer, the store operator picks which machine to clean. Arnar wants to minimize the total number of cleanings. Arnar knows everyone in the queue and the flavour each person wants. The store has a strict no-cutting policy, so customers are served in arrival order. Find the minimum number of cleanings needed to serve all $n$ customers, including Arnar. Initially every machine is empty and must be cleaned before its first flavour. Once a machine is loaded with a flavour, it can serve any number of customers who want that flavour until it is cleaned and loaded with another flavour. A machine that is never used does not need cleaning.

Input

The first line has three integers $n$ , $m$ , and $k$ : the number of customers in the queue, the number of flavours, and the number of ice cream machines. Each of the next $n$ lines contains an integer $c_i$ ( $1 \leq c_i \leq m$ ), the flavour wanted by the $i$ -th customer in the queue.

Output

Output the minimum total number of cleanings needed to serve all $n$ customers.

Examples2

Example 1
Input
```
8 3 1
2
3
3
1
2
1
1
3
```
Expected output
```
6
```
Example 2
Input
```
8 3 2
2
3
3
1
2
1
1
3
```
Expected output
```
4
```