比赛链接

给定一个长度为 $n$ 的序列 $\{a\}$，每次操作可以任取一个位置并将该位置的数移到序列末尾。

问最少需要多少次操作才能使序列中所有大小相同的数相邻。

显然只需要在序列中选定一些位置，然后按特定顺序将他们移除就可以完成任务。定义 $\text{dp}(i)$ 表示不选择序列 $[i,n]$ 中的位置个数的最大值。

维护每个值 $v$ 的最靠左出现的位置 $l_v$，最靠右出现的位置 $r_v$，动态维护 $[i,n]$ 中出现的次数 $c_v$。

如果保留位置 $i$ 并将其作为 $[1,n]$ 中所有值等于 $a_i$ 且不移动的位置中最靠左的位置，则

若 $i=l_{a_i}$，则需要移除 $[i,r_{a_i}]$ 中所有不等于 $a_i$ 的位置，即 $\text{dp}(i)=c_{a_i}+\text{dp}(r_{a_i}+1)$。

若 $i\neq l_{a_i}$，因为 $i$ 是 $[1,n]$ 中所有值等于 $a_i$ 且不移动的位置中最靠左的位置，于是 $l_{a_i}$ 的位置的数强制移动。

为了使得 $l_{a_i}$ 的位置的数与 $i$ 位置的数相邻，需要移除 $[i,n]$ 中所有不等于 $a_i$ 的位置，于是