洪水染色 - 代码源竞赛平台

题目描述

蜗蜗面前有一排 $n$ 个方格，第 $i$ 个方格的初始颜色为 $c_i$。相邻且颜色相同的方格连在一起，构成一个连通块。

开始时，蜗蜗可以任选一个方格作为起点，这一步不计入操作次数。之后每次操作，他可以把包含这个起点的整个连通块改成另一种颜色。如果改色后的连通块与相邻连通块颜色相同，它们会合并成一个更大的连通块。

请你求出最少需要多少次操作，才能使所有方格的颜色相同。

输入格式

第一行包含一个整数 $n$，表示方格的数量。

第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示每个方格的初始颜色。

输出格式

输出一行一个整数，表示使所有方格颜色相同所需的最少操作次数。

样例

3
1 2 1

1

样例解释

选择第 $2$ 个方格作为起点，将它所在连通块的颜色改为 $1$。此时三个方格的颜色都为 $1$，只需要操作一次。

数据范围

对于 100% 的数据，保证 $1\le n\le 5000$，$1\le c_i\le 5000$。