分数: 1100 点
问题陈述
给你一个整数序列 A=(A_1,A_2,\dots,A_N) 长度 N。在此序列上,可以执行以下操作:
- 选择 l 和 r (1\leq l < r \leq N) 这样 A_l=A_r, A_{l+1}=A_{l+2}=\dots=A_{r-1},和 A_{l+1}\neq A_l。替换每个 A_{l+1},A_{l+2},\dots,A_{r-1} 与 A_l。该操作的成本是 r-l-1.
您将重复此操作,直到没有 l 和 r (1\leq l < r \leq N) 这样 A_l=A_r, A_{l+1}=A_{l+2}=\dots=A_{r-1},和 A_{l+1}\neq A_l。求这一系列操作的最小总成本。
约束
- 3 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
7 1 2 3 2 3 2 1
示例输出 1
7
例如,如果您使用 (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.
示例输入 2
5 1 2 3 4 5
示例输出 2
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
示例输出 3
44