说明

现在有很多个带有颜色的圆球排列在一起，为了方便，我们用数字来表示圆球的颜色。现在交给你一个任务，选择某个位置的圆球作为起始圆球，然后每次你可以将包含这个起始圆球的颜色块（我们称连续的具有相同的颜色的圆球称为块，单个圆球也是块）变为它右边相邻的颜色块的颜色或变为它左边相邻的颜色块的颜色，问你，如何选择起始位置，才能用最少的次数将所有圆球都变为一个颜色，输出这个次数。

输入格式

第一行输入一个数n(1<=n<=5000)

第二行输入n个数，代表每个位置圆球的颜色

输出格式

输出一个数代表将所有圆球变为一个颜色所需的最少次数

样例

4
5 2 2 1

2

样例

8
4 5 2 2 1 3 5 5

4

样例

1
4

0