Problem: Toy Factory

Want to try solving this problem? You can submit your code online if you log in or register.

Toy Factory

Time Limit: 1 second
Memory Limit: 16 Mb

To pursue your artistic destiny, you have taken up a job as a painter in a toy factory in a small village in France. Your dream is to become a famous painter, remembered with the likes of Renoir and Monet. Unfortunately, at this toy factory, your job is much more menial. The factory produces the famous flip-flap toy. Flip-flaps come in many different colours, though each individual flip-flap is painted a single colour all over.

You are placed at the end of the factory line. On one side, you have the flip-flaps coming off the line that require painting. Each flip-flap must be painted its designated colour. On the other side, you have C tins of paint--one for each possible colour. Your dreary job is to simply paint each toy the correct colour.

Painting the toy is easy if the tin of paint required is already open. If the required tin of paint is not already open, you must fetch your screwdriver and open the lid before you can paint the toy. In addition, company policy dictates that no more than K tins of paint may be open simultaneously, as excessive paint fumes lead to strange dreams. Once you have exactly K tins of paint open, you must close one tin before opening another. No tins of paint are open to begin with.

Because opening tins of paint is a messy and tedious task, you wish to avoid it as much as possible. Given the colours of the toys to paint and the order in which you must paint them, your task is to find the fewest number of times you need to open a tin of paint, in order to paint them all the correct colour.

Constraints

For 100% of the available marks:

1 ≤ N ≤ 100,000, where N is the number of toys you are required to paint.
1 ≤ C ≤ 100,000, where C is the number of tins of paint, each containing a different colour of paint.
1 ≤ K ≤ C, where K is the maximum number of tins you may have open simultaneously.

Additionally, for 50% of these marks:

1 ≤ N ≤ 1000.

Input

Your program must read from standard input. The first line of input will contain the integers N C K, as described above. Each colour is assigned an integer 1, 2, ..., C.

The following N lines will describe the colour of each toy on the factory line, in the order you are required to paint them. Each of these lines will contain a single integer c_i, the colour the ith toy must be painted ( 1 ≤ c_i ≤ C).

Output

Your program must write a single line to standard output. This line must contain a single integer, giving the fewest number of times you need to open a tin of paint.

Sample Input

Sample Output

Explanation

In this example, you have four tins of coloured paint but can only have up to two tins open at a time. In order to paint the 10 toys, one possible sequence of opening and closing tins is shown below.

Toy colour	Tins open	Action performed
3	3	Opened tin 3.
4	3, 4	Opened tin 4.
2	2, 3	Closed tin 4, opened tin 2.
2	2, 3
3	2, 3
4	3, 4	Closed tin 2, opened tin 4.
1	1, 4	Closed tin 3, opened tin 1.
4	1, 4
3	3, 4	Closed tin 1, opened tin 3.
4	3, 4

This sequence requires opening tins of paint six times. This is also the fewest number possible.

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.