[COCI 2024/2025 #4] 鞋 / Cipele（疑似错题）

译自 [COCI 2024/2025 #4](https://hsin.hr/coci/) T4。$\texttt{2s,0.5G}$。满分为 $120$。 根据[讨论](https://codeforces.com/blog/entry/138804?#comment-1242632)，本题为错题，可能不存在靠谱做法。

有 $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$。 | 子任务编号 | $n,m\le$ | $q\le $ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: |:--: | | $ 1 $ | $10^3$ | $10^3$ | |$ 17 $ | | $ 2 $ | $2\times 10^5$ | $10^6$ | A |$ 27 $ | | $ 3 $ | $2\times 10^5$ | $10^6$ | B |$ 37 $ | | $ 4 $ | $2\times 10^5$ | $2\times 10^5$ | |$ 24 $ | | $ 5 $ | $2\times 10^5$ | $10^6$ | |$ 15 $ | - 特殊性质 A：$n=m$。 - 特殊性质 B：$m=0$。