← 返回题目列表

Codeforces · 1114/D

D. 洪水填充

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

您会看到一行 $$$n$$$ 彩色方块,从左到右编号为 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 个方块最初的颜色为 $$$c_i$$$。

假设,如果 $$$c_i = c_j$$$ 且 $$$c_i = c_k$$$ 对于所有满足 $$$i < k < j$$$ 的 $$$k$$$,则两个方格 $$$i$$$ 和 $$$j$$$ 属于同一连通分量。换句话说,从 $$$i$$$ 到 $$$j$$$ 段上的所有方块都应该具有相同的颜色。

例如,$$$[3, 3, 3]$$$ 行有 $$$1$$$ 个连通分量,而 $$$[5, 2, 4, 4]$$$ 行有 $$$3$$$ 个连通分量。

游戏“洪水填充”在给定线上进行,如下所示:

- 在游戏开始时,您选择任何起始方格(这不计为回合)。
- 然后,在每个游戏回合中,将包含起始方块的连接组件的颜色更改为任何其他颜色。

求整条线变成单色所需的最少匝数。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 方格数。

第二行包含整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 5000$$$) — 方块的初始颜色。

输出

打印一个整数——所需的最小圈数。

示例

输入 #1

4
5 2 2 1

输出 #1

2

输入 #2

8
4 5 2 2 1 3 5 5

输出 #2

4

输入 #3

1
4

输出 #3

0

注意

在第一个示例中,实现最佳答案的一种可能方法是选择索引为 $$$2$$$ 的方格作为起始方格,然后按如下方式播放:

- $$$[5, 2, 2, 1]$$$
- $$$[5, 5, 5, 1]$$$
- $$$[1, 1, 1, 1]$$$

在第二个示例中,实现最佳答案的一种可能方法是选择索引为 $$$5$$$ 的方块作为起始方块,然后按顺序重新着色为颜色 $$$2, 3, 5, 4$$$。

在第三个示例中,线条已仅包含一种颜色。