It costs a long time for CPUs to access data from memory, so most of CPUs have caches where requests for data can be served faster. To be cost-effective and to enable efficient use of data, caches must be relatively small. Therefore, we must use some policies to choose some data wisely and storage them in the cache. We divide the memory into many blocks which have the same size and index them from 1 to $$$10^9$$$, and every block has an unique index. A cache will have a capacity for $$$K$$$ blocks, which means it can storage at most $$$K$$$ blocks simultaneously. A cache hit occurs when the requested block is available in the cache, or we say a cache miss occurs. Now we introduce a LRU (Least Recently Used) placement policy on a fully associative cache.

1. If the requested block is available in the cache, a cache hit occurs.
2. If not, CPU can only access the block from the memory and write the block into the cache. If cache is not full, append the block into the cache.
3. If the cache is full, cache is full, the block which haven't been visited for the longest time in the cache will be replaced by the new block.

An example for cache with capacity of $$$3$$$ blocks is shown below.

The $$$8^{th}$$$, $$$4^{th}$$$ and $$$3^{rd}$$$ are in the cache when the $$$6^{th}$$$ block is requested, so a cache miss occurs. At that time, the cache is full, and we must decide the block to be replaced. The most recent request of $$$8^{th}$$$ block is the $$$13^{th}$$$ request, the most recent request of $$$4^{th}$$$ block is the $$$14^{th}$$$ request and the most recent request of $$$3^{rd}$$$ block is the $$$11^{th}$$$ request. The $$$3^{rd}$$$ block will be replaced by the $$$6^{th}$$$ block because the $$$3^{rd}$$$ block hasn't been visited for longest time.

Now the sequence of requested blocks and the capacity of the cache are given, please determine the minimum capacity for the cache in order to ensure at least K requests to hit the cache.