题目描述

给定一排彩色方块，从左到右编号为 $1$ 到 $n$。第 $i$ 个方块初始颜色为 $c_i$。

如果两个方块 $i$ 和 $j$ 满足 $c_i = c_j$，且对于所有满足 $i \lt k \lt 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$）— 方块的数量。

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

输出格式

输出一个整数 — 所需的最少回合数。

样例

4
5 2 2 1

2

8
4 5 2 2 1 3 5 5

4

1
4

0

说明/提示

样例解释

在第一个示例中，实现最佳答案的一种可能方式是选择下标为 $2$ 的方块作为起始方块，然后按以下步骤进行：

• \[5, 2, 2, 1\]
• \[5, 5, 5, 1\]
• \[1, 1, 1, 1\]

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

在第三个示例中，排列已经只包含一种颜色。