C0759 博弈游戏（2603-6）

博弈游戏（2603-6）

题目描述

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

• 若双方选择的数字相同，本轮为平局；
• 若数字不同，胜负遵循固定克制关系：1克制2，2克制3，3克制1，被克制的一方本轮落败，克制的一方本轮获胜。

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

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

1. 任何一轮都不能落败（即每一轮只能获胜或平局）；
2. 不能连续两轮选择相同的数字出招；
3. 在满足前两个条件的前提下，尽可能多地获得轮次的胜利。

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

输入

第一行：一个整数表示n

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

输出

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

数据范围

1≤n≤2×10^5，si∈{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