Description

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

The principle of this translation software is very simple. It processes the text sequentially from start to finish, replacing each English word with its corresponding Chinese meaning. For each English word, the software first checks if the word's Chinese meaning is present 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 for translation, and then stores both the word and its translation in memory for future reference.

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 place the new word into an unused memory unit. If the memory already contains M words, the software will clear the earliest word that was stored in memory to free up a unit for the new word.

Suppose an English article consists of N words. Given this article to be translated, how many times will the translation software need to access the external dictionary? Assume that the memory initially contains no words before translation begins.

Input Format

The input consists of 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, arranged in the order of the article. Each integer (not exceeding 1000) represents an English word. Two words in the article are considered the same if and only if their corresponding integers are identical.

Output Format

The output consists of a single line containing an integer, which represents the number of times the software needs to access 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