Optimal Cache Replacement Strategy

In modern computer systems, the CPU can exchange data only with the high-speed cache. When a requested memory cell is not found in the cache, it must be loaded from the main memory. If the cache is full, one of its entries must be removed. A common strategy is the Least Recently Used (LRU) algorithm, but it is not always optimal.

Given an initially empty cache of fixed capacity and a sequence of main memory access requests, determine the minimum number of cache misses possible if, on every miss, the optimal memory cell is removed.

The optimal strategy is as follows: when a cache miss occurs and the cache is full, evict the memory cell that is either never used again or used farthest in the future. In mathematical terms, for each element x in the cache, let $$d(x)$$ denote the distance (in access requests) from the current time until the next occurrence of x (with $$d(x)=\infty$$ if x does not occur anymore). Evict the element with the maximum $$d(x)$$.

inputFormat

The first line of input contains two integers n and m separated by a space, where n is the capacity of the cache and m is the number of memory access requests.

The second line contains m integers, representing the sequence of main memory addresses accessed.

outputFormat

Output a single integer: the minimum number of cache misses occurring when using the optimal cache replacement strategy.

sample

3 6
10 20 10 21 31 10

4