题目背景

译自 COCI 2024/2025 #4 T4。$\texttt{2s,0.5G}$。满分为 $120$。

根据讨论，本题为错题，可能不存在靠谱做法。

题目描述

有 $n$ 双鞋，标号 $1\sim n$。鞋柜是一个栈，初始鞋都在鞋柜中，从栈顶到栈底依次是第 $1,2,\ldots,n$ 双鞋。

接下来 $q$ 天，第 $i$ 天要穿标号为 $a_i$ 的鞋。如果这双鞋是栈顶到栈底第 $j$ 双鞋，则需要 $j$ 秒将其拿出（不改变其他鞋的相对顺序）；如果这双鞋在走廊里，则不花费时间。

每天结束时，可以选择将标号为 $a_i$ 的鞋入栈，或者放在走廊里。走廊里至多能放 $m$ 双鞋。

额外地，除了取鞋的过程中，随时都可以从走廊取任意多双鞋（以任意顺序）入栈。

试最小化取鞋用的总时间。

输入格式

第一行，三个整数 $n,m,q$。

第二行，$q$ 个正整数 $a_1,a_2,\ldots,a_q$。

输出格式

输出一行一个正整数，表示答案。

5 1 6
2 1 2 1 2 1

5

6 0 4
5 4 3 4

17

3 2 7
1 2 3 2 3 1 3

4

提示

样例解释

样例 $1$ 解释：第 $1$ 天时取第 $2$ 双鞋并放在走廊。穿完第 $1$ 双鞋后立刻放入栈中。不难发现这样只需要 $2+1+0+1+0+1=5$ 秒。

提示

对于 $100\%$ 的数据，保证：

• $1\le n\le 2\times 10^5$；
• $0\le m\le 2\times 10^5$；
• $1 \le q\le 10^6$；
• $1\le a_i\le n$。

• 特殊性质 A：$n=m$。
• 特殊性质 B：$m=0$。