P3419 [POI 2005] SAM-Toy Cars

Jasio is a three-year-old boy who loves to play with toy cars. He has $n$ toy cars stored on a shelf. Jasio cannot reach the toy cars on the shelf, but he can reach the ones on the floor. Jasio’s mother helps by moving toy cars from the shelf to the floor. The floor can hold at most $k$ toy cars. When there are already $k$ toy cars on the floor, Jasio’s mother will first take one toy car from the floor back to the shelf, and then bring the toy car that Jasio wants. Now Jasio wants to play with $p$ toy cars in order. Determine the minimum number of times his mother needs to take a toy car down. (Only count taking down from the shelf; do not count putting back.)

The first line contains three integers $n$, $k$ and $p$. The next $p$ lines each contain exactly one integer $a_i$, indicating the ID of the toy car Jasio wants.

Output a single integer, the minimum number of times Jasio’s mother needs to take a toy car down.

Constraints: For $100\%$ of the testdata: $1 \le k \le n \le 10^5$, $1 \le p \le 5 \times 10^5$, $1 \le a_i \le n$. Translated by ChatGPT 5