Description

In a computer, the CPU can exchange data directly only with the Cache. When the required main memory block is not in the Cache, the data must be brought in from main memory. If the Cache is already full at that time, one block must be removed first.

For example, suppose the Cache capacity is $3$, and it currently holds main memory blocks numbered $10$ and $20$.
Now, the CPU accesses block $10$, which is a cache hit.

Next, the CPU accesses block $21$, so we just bring that block into the Cache, causing one cache miss.

Then, the CPU accesses block $31$, so one block must be evicted from the Cache before bringing block $31$ in. Suppose we evict block $10$.

After that, the CPU accesses block $10$ again, which causes another miss. We can see that if we had evicted a different block the previous time, we could have avoided this miss.

Modern computers often use the LRU (Least Recently Used) algorithm for Cache management—but as the example shows, it is not optimal.
Given an empty Cache with fixed capacity and a sequence of main memory access requests, Congcong wants to know which block to evict on each cache miss to minimize the total number of cache misses.

Input Format

The first line contains two integers $N$ and $M$ ($1 \le M \le N \le 10^5$), representing the number of main memory accesses and the capacity of the Cache.

The second line contains $N$ space-separated positive integers, giving the ID of each main memory block in access order (each does not exceed $10^9$).

Output Format

Output one line: the minimum possible number of cache misses.

6 2
1 2 3 1 2 3

4

Hint

On the $4$-th miss, evict block number $3$ from the Cache.

Translated by ChatGPT 5