Toy Cars

Johnny is a little boy, only three years old, and he loves playing with toy cars. He owns $n$ different cars, all kept on a shelf so high that he cannot reach them by himself. His room is small, so at no moment may there be more than $k$ toy cars on the floor.

Johnny plays with one car from the floor at a time. His mother stays in the room with him the whole time. When Johnny wants another car that is already on the floor, he reaches it himself. But when the car he wants is on the shelf, his mother has to hand it to him. Whenever she gives him a car, she may at the same time pick any one car from the floor and put it back on the shelf, so that there is always enough room on the floor.

His mother knows him so well that she can perfectly predict which cars Johnny will want to play with, and in what order. Using this knowledge, she wants to minimize the number of times she has to hand a car down from the shelf. To do so she must choose very carefully which car to put back on the shelf each time.

Write a program that reads the sequence of cars Johnny will want to play with, in order, and computes the minimal number of times his mother has to take a car from the shelf.

The first line contains three integers $n$, $k$, $p$ ($1 \le k \le n \le 100{,}000$, $1 \le p \le 500{,}000$), separated by single spaces: the total number of cars, the maximum number of cars that may be on the floor at once, and the length of the sequence of cars Johnny will want to play with. Each of the next $p$ lines contains one integer — the number of a car Johnny will want to play with (the cars are numbered from $1$ to $n$).

Print a single integer: the minimal number of times his mother has to take a car from the shelf.