2119. Seamild迎奥运

单点时限: 5.0 sec

内存限制: 256 MB

今天奥运圣火经过我们学校,规定参观奥运圣火的同学的衣服颜色不能很混乱:同学应排成一横排,且衣服颜色必须是左右对称的。

例如:“红蓝绿蓝红”或“红蓝绿绿蓝红”都是符合的,而“红蓝绿红”或“蓝绿蓝红”就不符合要求。

参观奥运圣火的人数自然很多,仅现有的同学就可能会有 3000 个。Seamild 希望将队形调整得符合要求,但想要调整尽量少,减少麻烦。以下任一动作认为是一次调整:

1、在队伍左或右边加一个人(衣服颜色依要求而定);

2、在队伍中任两个人中间插入一个人(衣服颜色依要求而定);

3、剔掉一个人;

4、让一个人换衣服颜色;

Seamild 想知道就目前的队形最少的调整次数是多少,请你编一个程序来回答她。

因为大家都想观看奥运圣火,你可以认为人数是无限的,即随时想加一个人都能找到人。同时衣服颜色也是任意的 .

输入格式

第一行是一个整数 n(1≤n≤3000)。

第二行是 n 个整数,从左到右分别表示现有的每个同学衣服的颜色号,都是 1 到 3000 的整数。

输出格式

一个数,即对于输入队列,要调整得符合要求,最少的调整次数。

样例

Input
4
1 2 3 2
Output
1
Hint:在最右边添加一个1就能对称了.

16 人解决,43 人已尝试。

21 份提交通过,共有 110 份提交。

6.7 EMB 奖励。

创建: 16 年,6 月前.

修改: 7 年,3 月前.

最后提交: 2 年,5 月前.

来源: N/A

题目标签