На главной улице Берлятова стоит одноэтажный дом, в котором есть \(n\) квартир. Вова наблюдает за этим домом каждую ночь. Дом может быть представлен как массив, состоящий из \(n\) целых чисел \(a_1, a_2, \dots, a_n\), где \(a_i = 1\), если в \(i\)-й квартире включен свет, и \(a_i = 0\) иначе.
Вова думает, что жильцы \(i\)-й квартиры обеспокоены и не могут спать тогда и только тогда, когда \(1 < i < n\) и \(a_{i - 1} = a_{i + 1} = 1\) и \(a_i = 0\).
Вова задался следующим вопросом: чему равно минимальное число \(k\) такое, что если жильцы ровно \(k\) попарно различных квартир выключат свет, то никто не будет обеспокоен? Ваша задача — найти это число \(k\).
Выходные данные
Выведите одно целое число — минимальное число \(k\) такое, что если жильцы ровно \(k\) попарно различных квартир выключат свет, то никто не будет обеспокоен.
Примечание
В первом тестовом примере жильцы из квартир \(2\) и \(7\) или из квартир \(4\) и \(7\) могут выключить свет, и никто не будет обеспокоен. Можно показать, что нельзя добиться лучшего ответа на этот тестовый пример.
Во втором и третьем тестовых примерах нет обеспокоенных жильцов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
1 1 0 1 1 0 1 0 1 0
|
2
|
|
2
|
5
1 1 0 0 0
|
0
|
|
3
|
4
1 1 1 1
|
0
|