Problem E
Introspective Caching

Photo by suneko on Flickr

However, caches have a nasty tendency to fill up, so at some point, objects must be evicted from the cache to make room for new objects. Choosing what object to remove from the cache is not easy and there are several different algorithms to choose from.

The marvelous Apes in Computing Machinery have come up with a fantastic new algorithm, the Introspective Caching Algorithm, named after a city of Peru. It consists of some extra hardware (a very small, precognitive monkey) which helps making decisions. Since the monkey can see into the future, she knows exactly what objects will be accessed and in what order, and using this information she will make optimal decisions on what objects to remove from the cache. Optimality here means that she will minimize 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 was 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.

You have been tasked with evaluating the monkey’s performance, and feeding her the occasional banana.

Input

The first line of input contains three integers, separated by single spaces, telling you how many objects fit in the cache, $0 < c \le 10\, 000$, how many different objects are in the system, $c \le n \le 100\, 000$, and how many accesses, $0 \le a \le 100\, 000$, will occur. The following $a$ lines contain a single integer between $0$ and $n-1$ (inclusive) indicating what object is accessed. The first line corresponds to the first object accessed access and the last line to the last.

Output

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

1 2 3
0
0
1

2

3 4 8
0
1
2
3
3
2
1
0

5