题目描述

有一个长度为 $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$

输出格式

请输出答案。

样例 1

输入

7
1 2 3 2 3 2 1

输出

7

样例 2

输入

5
1 2 3 4 5

输出

0

样例 3

输入

40
1 2 3 4 5 6 7 8 7 6 5 6 7 8 7 6 5 4 3 2 2 1 2 3 4 5 4 5 6 7 8 7 7 6 5 6 6 7 8 8

输出

44

说明/提示

限制条件

• $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 翻译