P4404 [JSOI2010] 缓存交换

感谢 @ACdreamer 贡献数据

在计算机中，CPU 只能和高速缓存 Cache 直接交换数据。当所需的内存单元不在 Cache 中时，则需要从主存里把数据调入 Cache。此时，如果 Cache 容量已满，则必须先从中删除一个。 例如，当前 Cache 容量为 $3$，且已经有编号为 $10$ 和 $20$ 的主存单元。 此时，CPU 访问编号为 $10$ 的主存单元，Cache 命中。 接着，CPU访问编号为 $21$ 的主存单元，那么只需将该主存单元移入 Cache 中，造成一次缺失（Cache Miss）。 接着，CPU访问编号为 $31$ 的主存单元，则必须从 Cache 中换出一块，才能将编号为 $31$ 的主存单元移入 Cache，假设我们移出了编号为 $10$ 的主存单元。 接着，CPU再次访问编号为 $10$ 的主存单元，则又引起了一次缺失。我们看到，如果在上一次删除时，删除其他的单元，则可以避免本次访问的缺失。 在现代计算机中，往往采用 LRU（最近最少使用）的算法来进行 Cache 调度——可是，从上一个例子就能看出，这并不是最优的算法。 对于一个固定容量的空 Cache 和连续的若干主存访问请求，聪聪想知道如何在每次 Cache 缺失时换出正确的主存单元，以达到最少的 Cache 缺失次数。

输入文件第一行包含两个整数 $N$ 和 $M$ （$1 \le M \le N \le 10^5$），分别代表了主存访问的次数和 Cache 的容量。 第二行包含了N个空格分开的正整数，按访问请求先后顺序给出了每个主存块的编号（不超过 $10^9$）。

输出一行，为 Cache 缺失次数的最小值。

在第 $4$ 次缺失时将 $3$ 号单元换出 Cache。