LRUCACHE - LRU cache

no tags 

Implement the LRU cache replacement algorithm.

Input

The input consists of two lines. The first of these lines gives the size of the cache. The second of these lines describes a sequence of memory accesses. The sequence is described by N followed by x1, ..., xN: N is the length of the sequence, and each xk is a memory address.

The input is made out of whitespace-separated integers. All integers are positive and at most a million.

Output

The number of cache faults.

Example

Input:
2
5 1 2 1 3 1

Output:
3

We are supposed to simulate a LRU cache of size 2. The first two memory accesses cause faults, and locations 1 and 2 are loaded into the cache. The third access, to address 1, does not cause a fault. The fourth access, to location 3, causes a fault and location 3 is loaded into the cache as well; but, first, to make room for the value at address 3, location 2 is evicted. Location 2 is evicted because it is the oldest one to have been used -- this is what LRU means. Finally, the fifth access does not cause a fault, because location 1 is still in the cache.

In total, there are 3 faults.

See also: FIFOCACH and MINCACHE.



Added by:Radu Grigore
Date:2016-03-29
Time limit:1s-2s
Source limit:11000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:folklore