← 返回题目列表

AtCoder · joi2009yo_c

C. 链条

中文机器翻译题面 查看原题

配点: 100 点

問題

有一个游戏如下。

字符是垂直的 1 栏目 N 排成一排。这些字符的颜色是红色、蓝色或黄色,相同颜色的字符最初是 4 连续的数量不超过两个。玩家可以选择某个位置的角色并将其更改为另一种颜色。通过此操作,相同颜色的字符 4 如果两个或多个字符排成一行,这些字符将会消失。当一个角色消失时,会出现一个相同颜色的新角色。 4 如果超过四个字符连续排列,这些字符也会消失,并且这个链条将继续下去,直到不再有四个或更多相同颜色的字符连续排列为止。这个游戏的目标是尽量减少剩余角色的数量而不消失。

比如下图最左边的状态, 当您将第 6 个字符的颜色从黄色更改为蓝色时,蓝色字符变为 5 是连续的,所以它们消失了,最后 3 一个字符仍然存在,没有消失。

初始状态 当给出 N 字符的颜色序列时,1 仅在一处更改字符颜色时剩余不消失的最小字符数 编写一个程序来查找 M 。


入力

1 行是字符数 它仅由 N (1 \leqq N \leqq 10\,000组成。继续 N 行有 1, 2, 3 任何一个 1 整数被写入,i + 1 行目 (1 \leqq i \leqq N) 是从上面的初始状态 代表第 i 个字符的颜色(1 为红色,2 是蓝色的,3 代表黄色)。

出力

剩余不消失的最小字符数 输出 M 。


入力例 1

12
3
2
1
1
2
3
2
2
2
1
1
3

出力例 1

3

入力例 2

12
3
2
1
1
2
3
2
1
3
2
1
3

出力例 2

12