← 返回题目列表

AtCoder · arc181_f

F. 彩色黑白棋

中文机器翻译题面 查看原题

分数: 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