[POI2005] SAM-Toy Cars
题目描述
Jasio 是一个只有三岁的小男孩,他喜欢玩玩具车。他有 $n$ 辆玩具车被保存在书架上。
架子上的玩具车 Jasio 拿不到,但地板上的他可以拿到。Jasio 的母亲会帮 Jasio 拿架子上的玩具车到地板上。
地板最多只能放 $k$ 辆玩具车。
当地板已经放了 $k$ 辆玩具车时,Jasio 的母亲都会从地板上先拿走一个玩具车放回书架,再拿来 Jasio 想要的玩具车。
现在 Jasio 一共想依次玩 $p$ 个玩具车,问 Jasio 的母亲最少需要拿几次玩具车。(只算拿下来的,不算拿上去的)
输入输出格式
输入格式
第一行三个整数 $n,k$ 和 $p$。
接下来 $p$ 行,每一行有且仅有一个整数 $a_i$,表示 Jasio 想玩的玩具玩家车编号。
输出格式
输出一行一个整数,表示最少 Jasio 的母亲最少需要拿玩家车的次数。
输入输出样例
输入样例 #1
3 2 7
1
2
3
1
3
1
2
输出样例 #1
4
说明
对于 $100\%$ 的数据:$1\le k\le n\le 10^5$,$1\le p\le 5\times 10^5$,$1\le a_i\le n$。