Machine Translation Dictionary Lookup

In this problem, a simple machine translation software replaces each English word with its corresponding Chinese translation. The translation process works as follows:

• The software maintains a memory cache with capacity \(M\). Each slot can store one word and its translation.
• When a word is encountered in the article (of \(N\) words):
1. If the word is already in the cache, no dictionary lookup is performed.
2. If it is not in the cache, the software looks up the word in an external dictionary (counting as one lookup) and then stores the word and its translation in memory.
• If there is an empty slot (i.e. less than \(M\) words stored), the new word is added into an unused slot.
• If the cache is full (i.e. exactly \(M\) words), the software removes the word that has been in memory the longest (FIFO order) before adding the new word.

Your task is to compute the total number of dictionary lookups required to translate the entire article, assuming the cache is initially empty.

The process can be summarized by the following algorithm:

\[ \text{for each word in article:} \quad \text{if word not in cache then} \quad \text{lookup++, add word (remove oldest if full)} \]

inputFormat

The input consists of:

• The first line contains two integers: \(M\) (the cache capacity) and \(N\) (the number of words in the article).
• The second line contains \(N\) space-separated words, representing the English article.

outputFormat

Output a single integer: the total number of dictionary lookups performed.

sample

3 6
i love you i hate you

4