Problem B
Sock Line

Lina has just finished washing and has hung up $N$ socks on a clothesline. There are socks in $C$ different colors, and Lina is very particular about pairing the socks by color. Now it’s time to collect the socks, but since there are many socks, she can’t carry them all at once. She could, of course, walk back and forth among the socks and pair some at a time, but Lina is very lazy and thinks that seems too much effort. Therefore, she uses her quick-sort strategy instead.

The strategy works as follows: She takes an IKEA bag that can hold $M$ socks and walks from left to right along the clothesline. Each time she picks up a new sock from the line, she can either choose to pair it with one of the socks already in the IKEA bag (and the pair does not go into the bag) or she can place the new sock into the bag. If the bag is full, she must discard one of the socks already in the bag to make room for the new one; otherwise, she must discard the new sock. How many pairs of socks can Lina maximally pair using her strategy?

Input

The first line contains three integers, $N$, $M$, $C$ $(2 \leq N \leq 10^5), (1 \leq M, C \leq N)$. $N$ is the number of socks on the clothesline, $M$ is the maximum number of socks that can fit in the IKEA bag, and $C$ is the number of different colors the socks can have.

Then follows a line containing $N$ integers, describing the color of the socks hanging on the clothesline. The number $n_i$ $(1 \leq n_i \leq C)$ indicates that the $i$-th sock has color $n_i$.

Output

Print an integer, the maximum number of pairs of socks that Lina can create.

Scoring

Your solution will be tested on several different test groups. To earn points for a group, you must pass all test cases in the group.

Explanation

In the first example case, you can first place socks of colors 2, 3, and 3 in the bag. Then you pair the socks with color 3. This leaves one sock with color 2 in the bag. Afterward, you place the socks with colors 2 and 1 into the bag and pair them with the sock of color 2, leaving one sock of color 1 in the bag. Finally, you place the last sock of color 1 in the bag and pair them. In total, this results in three pairs of socks.

In the second example case, only one sock can fit in the bag. You first place the sock of color 2 in the bag. Then, the next sock is of color 1. Since the bag is full, you must discard one sock. If you discard the sock of color 2, you can place the sock of color 1 into the bag and then pick up the next sock, which also has color 1, and pair it with the sock in the bag. This is the only pair you can make, so the answer is 1.

6 3 3
2 3 3 2 1 1

3

4 1 3
1 2 1 3

1

8 4 2
1 1 2 1 2 1 1 1

4