前情提要：贪心被样例打假发现要 DP，脑子一抽先不压维写二维的看看正确性再压维，然后没调出来。

事后发现写了一车 BUG ，有一半是因为写二维 DP 出来的，剩下的包括转移顺序错误以及多测清空不彻底。

又寄了，上绿失败。

少废话进正题。

首先有个比较显然的性质：每次删除的数一定单调递减，更具体地，删除的值都小于当前的 $mex$。

证明很简单，每次删除的贡献是 $mex$，想要减小贡献就得尽快减小 $mex$，根据其性质删 $\ge mex$ 的数完全是找茬的。

这时候如果贪心删除每次 $\lt mex$ 的出现次数最多的数会被样例的第四组给扬了。还能怎么办？没后效性最优子结构贪不了直接 DP 呗，反正这题 $n \le 5000$。

预处理一下，把 $\ge mex$ 的数全部踢掉，剩下的数递增排序并离散化，设第 $i$ 个数为 $a_i$，它出现了 $b_i$ 次。特判一下初始 $mex=0$ 的情况，这样完全不需要 DP 处理。

DP 状态，一开始我写了个很丑陋的二维状态：$dp_{i,j}$ 表示第 $i$ 次删除第 $j$ 个数的最小花费，写完了发现第一维屁用没有可以压，就想着先留着试试万一假了，属于是给自己埋伏笔了。

不用管谁是第几个被删除的，因为删除一定是有序的，这也不是什么背包问题，写了转移方程更会发现第一维一点用没有，去掉。

设 $dp_i$ 为按照上述预处理后删掉第 $i$ 个数即 $a_i$ 时的花费，按照上述预处理且特判后答案是 $dp_1$，因为一定有 $a_1=0$。

转移方程：预处理

$dp_i=mex\times (b_i-1)+a_i$

之后转移：

$dp_i=min\{dp_i,min_{j\gt i} \{dp_j+a_j\times(b_i-1)+a_i\}\}$

解释一下，注意计费是先删了重算 $mex$ 之后才计费，并且预处理后删完新的 $mex$ 就是 $a_i$。

注意一定要倒着转移，因为顺序是倒着更新的。

这个时候裸转移显然是 $\Theta(n^2)$ 的，确实可以直接莽过题，但是前面预处理用 std::deque 再加上斜率优化可以做到 $\Theta(n\log n)$，这题没必要就是了。

code 不放了，丢人。