D. 洪水填充

时间限制：$2$ 秒 内存限制：$256$ 兆字节

有一行共 $n$ 个带颜色的方格，从左到右编号为 $1$ 到 $n$。第 $i$ 个方格初始颜色为 $c_i$。

我们说两个方格 $i$ 和 $j$ 属于同一个连通块，当且仅当 $c_i=c_j$，并且对所有满足 $i<k<j$ 的 $k$ 都有 $c_i=c_k$。 换句话说，从 $i$ 到 $j$ 的整段方格颜色必须全部相同。

例如，序列 $[3,3,3]$ 有 $1$ 个连通块，而序列 $[5,2,4,4]$ 有 $3$ 个连通块。

在这行方格上进行“洪水填充”游戏，规则如下：

• 游戏开始时，你任选一个方格作为起点（这一步不计入操作次数）。
• 之后每一轮操作，你可以把起点所在的连通块整体染成任意一种其他颜色。

求把整行方格染成同一种颜色所需的最少操作次数。

---

输入格式

第一行一个整数 $n$（$1\le n\le 5000$），表示方格数量。

第二行 $n$ 个整数 $c_1,c_2,\dots,c_n$（$1\le c_i\le 5000$），表示每个方格的颜色。

---

输出格式

输出一个整数，表示所需的最少操作次数。

---

样例输入

4
5 2 2 1

8
4 5 2 2 1 3 5 5

1
4

样例输出

2

4

0

---

说明

在第一个样例中，最优方案之一是选择下标为 $2$ 的方格作为起点，然后按如下步骤染色：

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

在第二个样例中，最优方案之一是选择下标为 $5$ 的方格作为起点，然后依次染成颜色 $2,3,5,4$。

在第三个样例中，整行已经是同一种颜色，无需操作。