博弈游戏

题目描述

两位玩家进行回合制博弈游戏，游戏总计进行 n 轮。每一轮，双方都要从1、2、3三个数字中选择一个出招，胜负规则如下：

（1）若双方选择的数字相同，本轮为平局；

（2）若数字不同，胜负遵循固定克制关系：1克制2，2克制3，3克制1，被克制的一方本轮落败，克制的一方本轮获胜。

其中一位玩家提前掌握了对手的完整出招顺序——对手在第 i 轮选择的数字为 si，所有 si 组成一个长度为 n 的序列。

该玩家需要规划自己每一轮的出招，满足以下全部条件：

（1）任何一轮都不能落败（即每一轮只能获胜或平局）；

（2）不能连续两轮选择相同的数字出招；

（3）在满足前两个条件的前提下，尽可能多地获得轮次的胜利。

请计算该玩家最多能赢得的轮次数量。

输入格式

第一行：一个整数表示n。

第二行：n 个整数，表示s1、s2、……、sn，每个数为1、2或3。

输出格式

输出一个整数，表示玩家最多能赢得的游戏轮数。

输入样例#1

6
3 1 2 2 1 2

输出样例#1

5

输入样例#2

24
2 3 1 3 2 1 1 1 1 1 3 3 1 3 1 3 2 2 1 2 3 1 2 2

输出样例#2

18

说明提示：

1≤n≤200,000，si∈{1,2,3}

限制：

时间限制：1000ms，内存限制：256MiB