Introspective Caching

In a distributed system, data is never where you need it, and fetching data over a network takes time and consumes bandwidth. This can be mitigated by adding a cache: a node stores some resources locally, and if those resources are needed again it can take them from its cache instead of asking someone else for them.

Caches, however, tend to fill up, so at some point objects must be evicted to make room for new ones. Choosing which object to remove is not easy, and there are several different algorithms to choose from.

A research team has devised a new algorithm, the Introspective Caching algorithm, aided by a small helper that can see into the future. Because the helper knows exactly which objects will be accessed and in what order, it always makes the optimal decision about what to evict. Optimality here means it minimizes the number of times an object is read into the cache.

All object accesses go through the cache, so every time an object is accessed it must be inserted into the cache if it is not already there. All objects are of equal size, and no writes occur in the system, so a cached object is always valid. When the system starts, the cache is empty.

Given the sequence of accesses, compute the least number of times an object must be read into the cache under this optimal strategy.

The first line contains three integers separated by single spaces: the number of objects that fit in the cache $c$ ($0 < c \le 10000$), the number of different objects in the system $n$ ($c \le n \le 100000$), and the number of accesses $a$ ($0 \le a \le 100000$) that will occur.

The following $a$ lines each contain a single integer between $0$ and $n-1$ inclusive, indicating which object is accessed. The first line corresponds to the first access and the last line to the last.

Output the least number of times an object must be read into the cache to handle the accesses listed in the input.