AT_arc181_f.[ARC181F] Colorful Reversi

有一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$。对于该整数序列 $A$，可以进行如下操作：

• 选择满足 $A_l=A_r,\ A_{l+1}=A_{l+2}=\dots=A_{r-1},\ A_{l+1}\neq A_l$ 的 $l,r\ (1\leq l < r \leq N)$。将 $A_{l+1},A_{l+2},\dots,A_{r-1}$ 全部替换为 $A_l$。该操作的代价为 $r-l-1$。

当不存在满足 $A_l=A_r,\ A_{l+1}=A_{l+2}=\dots=A_{r-1},\ A_{l+1}\neq A_l$ 的 $l,r\ (1\leq l < r \leq N)$ 时，停止操作。请你求出一系列操作所需总代价的最小值。

输入以如下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\dots$ $A_N$

请输出答案。

限制条件

• $3 \leq N \leq 5 \times 10^5$
• $1 \leq A_i \leq N$
• 输入的所有值均为整数

样例解释 1

例如，依次进行 $(l,r)=(3,5),\ (2,6),\ (1,7)$ 的操作时，$A$ 会变为 $(1,2,3,2,3,2,1)\rightarrow (1,2,3,3,3,2,1)\rightarrow (1,2,2,2,2,2,1)\rightarrow (1,1,1,1,1,1,1)$，此时不存在满足条件的 $l,r$。这一系列操作的总代价为 $1+3+5=9$。另一方面，依次进行 $(l,r)=(2,4),\ (4,6),\ (1,7)$ 的操作时，$A$ 会变为 $(1,2,3,2,3,2,1)\rightarrow (1,2,2,2,3,2,1)\rightarrow (1,2,2,2,2,2,1)\rightarrow (1,1,1,1,1,1,1)$，这一系列操作的总代价为 $1+1+5=7$。

由 ChatGPT 4.1 翻译