Vasya有n天假期!因此,他决定提高自己的 IT 技能并参加体育运动。 Vasya 知道这 n 天的每一天的以下信息:该健身房是否开放以及当天是否在互联网上进行了比赛。对于第 i 天,有四种选择:
1. 这一天体育馆关闭,不进行比赛;
2、这一天健身房关闭,进行比赛;
3、这一天体育馆开放,不进行比赛;
4. 这一天体育馆开放,并进行比赛。
Vasya 每天都可以休息或参加比赛(如果在这一天进行),或者进行运动(如果健身房在这一天开放)。
求 Vasya 休息的最少天数(这意味着他不会同时进行运动和写作比赛)。 Vasya 唯一的限制是——他不想连续两天做同样的活动:这意味着,他不会连续两天做运动,也不会连续两天写比赛。
输入
第一行包含一个正整数 n (1 ≤ n ≤ 100) — Vasya 的假期天数。
第二行包含由空格分隔的整数序列 a1, a2, ..., an (0 ≤ ai ≤ 3),其中:
- 如果在假期的第 i 天健身房关闭并且不进行比赛,则 ai 等于 0;
- 如果在假期的第 i 天健身房关闭,但比赛进行,则 ai 等于 1;
- 如果在假期的第 i 天健身房开放并且没有进行比赛,则 ai 等于 2;
- 如果在假期的第 i 天健身房开放并且比赛进行,则 ai 等于 3。
输出
打印 Vasya 休息的最少天数。请记住,瓦夏拒绝了:
- 任意连续两天进行运动,
- 在任意连续两天内撰写比赛。
示例
输入 #1
4 1 3 2 0
输出 #1
2
输入 #2
7 1 3 3 2 1 2 3
输出 #2
0
输入 #3
2 2 2
输出 #3
1
注意
在第一次测试中,Vasya 可以在第一天参加比赛并在第三天进行运动。因此,他将只休息 2 天。
在第二次测试中,Vasya 应该在第 1、3、5 和 7 天进行比赛,在其他日子进行运动。这样一来,他就一天都不能休息了。
在第三次测试中,Vasya 可以在第一天或第二天进行运动。他不能在两天内进行运动,因为这将违反他的限制。这样一来,他就只能休息一天了。