Каникулы Васи будут длиться n дней! И Вася решил за это время улучшить свои навыки программирования, а также позаниматься спортом. Про каждый из n дней каникул Вася знает, будет ли открыт в этот день спортзал, а также будет ли в интернете в этот день проводиться контест. Для i-го дня возможны четыре варианта:
- в этот день закрыт спортзал и не проводится контест;
- в этот день закрыт спортзал и проводится контест;
- в этот день открыт спортзал и не проводится контест;
- в этот день открыт спортзал и проводится контест.
В каждый из дней Вася может либо отдыхать, либо писать контест (если он проводится в этот день), либо заниматься спортом (если открыт спортзал).
Перед вами стоит задача найти минимальное количество дней, в которые Вася будет отдыхать (то есть не будет заниматься спортом и не будет писать контест одновременно). Единственное ограничение от Васи — он не хочет два дня подряд заниматься одним и тем же видом активности, то есть он не будет заниматься спортом два дня подряд и он не будет писать контесты два дня подряд.
Выходные данные
Выведите минимально возможное количество дней, в которые Вася будет отдыхать. Помните, что Вася отказывается:
- заниматься спортом в какие-либо два подряд идущих дня,
- писать контест в какие-либо два подряд идущих дня.
Примечание
В первом тестовом примере Вася может написать контест в день номер 1 и позаниматься спортом в день номер 3. Таким образом, он будет отдыхать всего два дня.
Во втором тестовом примере Вася должен писать контесты в дни с номерами 1, 3, 5 и 7, а в остальные дни заниматься спортом. Таким образом, он не будет отдыхать ни одного дня.
В третьем тестовом примере Вася может позаниматься спортом либо в день номер 1, либо в день номер 2. Он не может заниматься спортом оба дня, так как это будет противоречить его ограничению. Таким образом, он будет отдыхать один день.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 3 2 0
|
2
|
|
2
|
7
1 3 3 2 1 2 3
|
0
|
|
3
|
2
2 2
|
1
|