Jasio's Toy Cars

Jasio is a three-year-old boy who loves playing with toy cars. He has n toy cars stored on a bookshelf that he cannot reach. However, he can pick up any car on the floor. His mother helps him by fetching the toy cars from the bookshelf onto the floor when needed.

The floor can hold at most k toy cars. When there are already k cars on the floor and Jasio wants a new toy car (one that is not on the floor), his mother will first remove one toy car from the floor (putting it back on the shelf) and then bring the desired toy car from the shelf to the floor. (Only the action of fetching a toy car from the shelf is counted.)

Jasio plans to play with p toy cars in a given order. Given the sequence of toy car requests (each represented by an integer between 1 and n), determine the minimum number of times his mother has to fetch a toy car from the bookshelf.

Note: Since his mother can choose which toy car on the floor to remove when the floor is full, an optimal strategy (knowing the entire sequence) should be used to minimize the number of fetch operations.

The optimal strategy is analogous to the optimal cache replacement algorithm. When a toy car is not already on the floor:

• If the number of cars on the floor is less than k, simply fetch the toy car.
• If the floor is full, remove the toy car that is either never used again or is used farthest in the future, then fetch the new toy car.

The total number of fetch operations (cache misses) is the answer.

inputFormat

The first line contains three integers n, k, and p separated by spaces, where:

• n is the total number of toy cars, numbered from 1 to n.
• k is the maximum number of toy cars that can be on the floor at any moment.
• p is the total number of toy car requests.

The second line contains p integers, representing the sequence of toy car requests in the order Jasio wants to play with them.

outputFormat

Output a single integer representing the minimum number of times Jasio's mother has to fetch a toy car from the bookshelf.

sample

3 2 6
1 2 3 2 1 2

4