CF1114D Flood Fill

给定一排 $n$ 个彩色方格，从左到右编号为 $1$ 到 $n$。第 $i$ 个方格初始颜色为 $c_i$。 我们称，如果 $c_i = c_j$，且对于所有满足 $i < k < j$ 的 $k$，都有 $c_i = c_k$，那么第 $i$ 个方格和第 $j$ 个方格属于同一个连通块。换句话说，从 $i$ 到 $j$ 的所有方格颜色都相同。 例如，序列 $[3, 3, 3]$ 只有 $1$ 个连通块，而序列 $[5, 2, 4, 4]$ 有 $3$ 个连通块。 现在在这排方格上玩“洪水填充”游戏，规则如下： - 游戏开始时，你可以任选一个起始方格（这一步不计入回合数）。 - 每一回合，你可以将包含起始方格的连通块的颜色更改为任意其他颜色。 请你求出，最少需要多少回合，才能将整排方格变成同一种颜色。

第一行包含一个整数 $n$（$1 \le n \le 5000$），表示方格的数量。 第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le 5000$），表示每个方格的初始颜色。

输出一个整数，表示最少需要的回合数。

在第一个样例中，一种达到最优的方法是选择第 $2$ 个方格作为起始方格，然后按如下方式操作： - $[5, 2, 2, 1]$ - $[5, 5, 5, 1]$ - $[1, 1, 1, 1]$ 在第二个样例中，一种达到最优的方法是选择第 $5$ 个方格作为起始方格，然后依次将颜色变为 $2, 3, 5, 4$。 在第三个样例中，序列已经全部为同一种颜色。 由 ChatGPT 4.1 翻译