有 $n$ 个砖块排成一排，从左到右编号为 $1 \sim n$。

其中，第 $i$ 个砖块的初始颜色为 $c_i$。

我们规定，如果编号范围 $[i,j]$ 内的所有砖块的颜色都相同，且当第 $i - 1$ 和 第 $j + 1$ 个砖块存在时，这两个砖块的颜色和区间 $[i, j]$ 的颜色均不同, 则砖块 $i$ 和 $j$ 属于同一个连通块。

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

现在，要对砖块进行涂色操作。

开始所有操作之前，你需要任选一个砖块作为起始砖块。

每次操作：

1. 任选一种颜色。
2. 将最开始选定的起始砖块所在连通块中包含的所有砖块都涂为选定颜色，

请问，至少需要多少次操作，才能使所有砖块都具有同一种颜色。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数 $c_1,c_2,…,c_n$。

输出格式

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

数据范围

前六个测试点满足，$1 \le n \le 20$。
所有测试点满足，$1 \le n \le 5000$，$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

输入样例4：

5
1 3 1 2 1

输出样例4：

3

样例4解释

注意，每次染色操作所涉及的连通块必须包含所有操作开始前选定的起始砖块。

因此，答案是 $3$，而不是 $2$。