Description

Xiao Chen has installed a machine translation software on his computer, which he often uses to translate English articles.

The principle of this translation software is very simple. It processes the text sequentially from start to end, replacing each English word with its corresponding Chinese meaning. For each English word, the software first checks if the word's Chinese meaning is in memory. If it is, the software uses it for translation; if not, the software looks up the word in an external dictionary, retrieves its Chinese meaning, translates it, and then stores both the word and its translation in memory for future lookups and translations.

Assume the memory has M units, each capable of storing one word and its translation. Whenever the software needs to store a new word in memory, if the number of words currently stored in memory does not exceed M−1, the software will store the new word in an unused memory unit. If the memory already contains M words, the software will clear the earliest word that entered the memory to free up a unit for the new word.

Suppose an English article has a length of N words. Given this article, how many times does the translation software need to look up the external dictionary? Assume that before translation begins, the memory contains no words.

Input Format

There are 2 lines. Numbers on each line are separated by a single space.

The first line contains two positive integers, M and N, representing the memory capacity and the length of the article, respectively.

The second line contains N non-negative integers, following the order of the article. Each number (not exceeding 1000) represents an English word. Two words in the article are considered the same if and only if their corresponding non-negative integers are identical.

Output Format

The output consists of 1 line, containing an integer that represents the number of times the software needs to look up the dictionary.

```input1 3 7 1 2 1 5 4 4 1 ``` ```output1 5 ``` ## Hint

【Data Range】

For 10% of the data, M=1 and N ≤ 5.

For 100% of the data, 0 < M ≤ 100 and 0 < N ≤ 1000.

Source

NOIP2010-S2-Day2-T1