样例下载

题目描述

书架上有 N 本互不相同的书，编号为 1 ~ N。

小明现在正坐在书桌前。

他想看书。

开始时，他的书桌上没有书，所以他需要站起来去书架上拿。

他每次去拿书，只会拿一本。拿到之后，他就会回到书桌前，坐下后看书。

如果他想看的书已经在书桌上了，他就不会起身去拿书了。

为了书桌上显得整洁，在任意时刻，他不希望自己的书桌上超过 M 本书。

他每次去拿书的时候，可以顺手将书桌上的一本书放回书架。当然，他也可以不这么做。

现在给出小明接下来依次要看的 K 本书的编号（可能有重复，即刚才看过的书，过会可能还想看），他要按顺序依次看这些书。

小明很懒，他不想太频繁地起身、坐下。

问：他最少需要起身多少次去书架上拿书？

输入

第一行：包含 3 个整数: N, M, K

接下来 K 行：每行一个整数，按顺序依次表示小明要看的书的编号

输出

一个整数，表示小明最少的起身拿书次数

样例输入

3 2 6
1
2
3
2
1
3

样例输出

4

样例解释

第一次：拿 1

第二次：拿 2

第三次：放回 1，拿 3

第四次：放回 2，拿 1

数据范围

$1 ≤ M ≤ N ≤ 10^5, 1 ≤ K ≤ 5×10^5$