rt

转移式：设 $f_i$ 表示删除若干个元素使得当前序列的 $\text{mex}$ 值为 $i$ 的最小代价，转移式为 $f_i=\min\{f_j+j\times (cnt_i-1)+i\}$，$cnt_i$ 表示满足 $a_j=i$ 的 $j$ 的个数。

考虑对这个式子进行优化：

当 $cnt_i\le cnt_j,i<j$ 时，删掉 $i$ 显然比删掉 $j$ 更优，此时 $f_j$ 这一状态显然不需要维护，而这一类位置可以用栈维护。将 $0$ 到 $k$ 依次试着加入栈，若此时的 $i$ 满足 $cnt_i<cnt_{top}$ 则入栈，容易发现栈内元素个数是 $O(\sqrt{n})$ 级别的，在栈上跑上述 $\text{dp}$ 即可。

问一下这个做法保真吗 如果假了能否给一组hack/kk

反正过了CF的数据

还有就是这种做法能不能交题解啊/kk