词典缓存

难度：T2

【知识点：队列】【知识点：模拟】

前置知识：数组、循环、分支、本单元对应队列操作

题目描述

内存最多保存 $C$ 个不同单词编号，起初为空。依次处理 $n$ 个编号：已经在内存中时不查词典、不改变顺序；不在时查词典一次，若内存已满先移除最早进入的编号，再把新编号加到末尾。求查词典次数。注意命中旧词不会把它移到末尾。

输入格式

第一行 $C,n$，第二行 $n$ 个单词编号。

输出格式

一行一个整数，表示查词典次数。

样例输入

3 7
1 2 1 5 4 4 1

样例输出

5

样例说明

容量为 $3$，表中内存编号按进入时间从早到晚排列。“命中”表示编号已在内存中，本次不查询，也不移动它的位置。

处理第三个输入编号 $1$ 时没有把它移到末尾，所以后来内存满时，最先移除的仍是 $1$。最后一次再次遇到它需要重新查询，因此答案是 $5$。

数据范围

$1\le C\le100$，$1\le n\le1000$，编号在 $1$ 到 $1000$ 之间。