题目描述

小晨的电脑上安装了一个机器翻译软件，用于翻译英语文章。

翻译软件的工作原理如下：

1. 按文章顺序依次处理每个英文单词，将其替换为对应中文含义
2. 查找中文含义的顺序：
   • 先在内存中查找，如果找到则直接翻译
   • 如果内存中没有，则去外存词典查找，并将该单词及译义存入内存
3. 内存管理：
   • 内存容量为 M，每个单元可存放一个单词和译义
   • 若内存未满，则将新单词存入空闲单元
   • 若内存已满，则清空最早进入内存的单词，为新单词腾出空间

已知一篇英语文章长度为 N，文章中的每个单词用一个非负整数表示（相同整数表示同一单词）。

请计算软件需要去外存查找词典的次数。假设翻译开始前，内存为空。

输入格式

• 第一行：两个正整数 M、N，分别表示内存容量和文章长度
• 第二行：N 个非负整数，按文章顺序表示单词

输出格式

输出一个整数，表示软件需要查词典的次数。

输入样例 #1

3 7  
1 2 1 5 4 4 1

输出样例 #1

5

题目说明

整个查字典过程如下（每行表示处理单词后的内存状况）：

• 空：内存初始为空
• 查找单词 1 并调入内存
• 查找单词 2 并调入内存
• 单词 1 已在内存中
• 查找单词 5 并调入内存
• 查找单词 4 并调入内存，替代最早进入的单词
• 单词 4 已在内存中
• 查找单词 1 并调入内存，替代最早进入的单词

共计查了 5 次词典。

数据范围与提示

• 对于小数据：M ≤ 10, N ≤ 1000
• 对于大数据：M ≤ 1000, N ≤ 100000