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.