#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/0C

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/0C

Repovive

Cache Miss Tracker - MAANG Problems | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

MAANG0C. Cache Miss Tracker

100 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Given a cache of capacity $K$ that uses the Least Recently Used (LRU) eviction policy, and a sequence of $N$ page references, count the total number of cache misses.

When a page is requested:

If the page is already in the cache (a hit): move it to the most recently used position.
If the page is not in the cache (a miss):
- If the cache is not full, add the page.
- If the cache is full, evict the least recently used page, then add the new page.

Return the total number of misses.

Constraints

$1 \le K \le N \le 200{,}000$
$1 \le \text{pages}[i] \le 10^9$

Input

\begin{array}{l} N \quad K \\ \text{pages}_0 \quad \text{pages}_1 \quad \cdots \quad \text{pages}_{N-1} \end{array}

Output

$ans$

Samples

Input

6 3
1 2 3 4 1 2

Explanation

Cache capacity $K=3$ . Page 1: miss (cache: [1]). Page 2: miss (cache: [1,2]). Page 3: miss (cache: [1,2,3]). Page 4: miss, evict LRU page 1 (cache: [2,3,4]). Page 1: miss, evict LRU page 2 (cache: [3,4,1]). Page 2: miss, evict LRU page 3 (cache: [4,1,2]). Total misses: 6.

Output

Input

7 3
1 2 3 1 2 3 4

Explanation

Cache capacity $K=3$ . Pages 1, 2, 3 cause three misses (cache: [1,2,3]). Page 1: hit, move to MRU (cache: [2,3,1]). Page 2: hit, move to MRU (cache: [3,1,2]). Page 3: hit, move to MRU (cache: [1,2,3]). Page 4: miss, evict LRU page 1 (cache: [2,3,4]). Total misses: 4.

Output

Input

8 2
1 2 1 3 2 3 1 2

Explanation

Cache capacity $K=2$ . Page 1: miss (cache: [1]). Page 2: miss (cache: [1,2]). Page 1: hit, move to MRU (cache: [2,1]). Page 3: miss, evict LRU page 2 (cache: [1,3]). Page 2: miss, evict LRU page 1 (cache: [3,2]). Page 3: hit, move to MRU (cache: [2,3]). Page 1: miss, evict LRU page 2 (cache: [3,1]). Page 2: miss, evict LRU page 3 (cache: [1,2]). Total misses: 6.

Output

Given a cache of capacity $K$ that uses the Least Recently Used (LRU) eviction policy, and a sequence of $N$ page references, count the total number of cache misses.

When a page is requested:

If the page is already in the cache (a hit): move it to the most recently used position.
If the page is not in the cache (a miss):
- If the cache is not full, add the page.
- If the cache is full, evict the least recently used page, then add the new page.

Return the total number of misses.

Constraints

$1 \le K \le N \le 200{,}000$
$1 \le \text{pages}[i] \le 10^9$

\begin{array}{l} N \quad K \\ \text{pages}_0 \quad \text{pages}_1 \quad \cdots \quad \text{pages}_{N-1} \end{array}

$ans$