Торнадо!#6594
Чи є ця шалена погода результатом постійного втручання людства в навколишнє середовище? Чи це просто нормальний цикл кліматичних змін протягом століть? Ніхто, здається, не знає напевно, але факт у тому, що природні явища, такі як торнадо та урагани, вражають нашу країну з більшою силою та частотою, ніж у минулі десятиліття.
Одне торнадо щойно вдарило по фермі Сільверадо, виробнику великої рогатої худоби та молока, і завдало шкоди. Дах сараю був зірваний, кілька дерев вирвано з коренем, фермерська вантажівка перекинута... Але найгірше те, що торнадо зруйнувало кілька секцій огорожі, яка оточувала власність. Огорожа була дуже добре побудована, з бетонними стовпами кожні два метри, і колючим дротом, що огороджував весь периметр ферми (периметр, у метрах, є парним числом, що робить огорожу ідеально регулярною).
Тепер кілька стовпів зламані або відсутні, і в огорожі є прогалини. Щоб запобігти виходу худоби з території, огорожу потрібно відновити якомога швидше. Відновлення огорожі до її початкової форми з бетонними стовпами займе багато часу. Тим часом власники ферми вирішили закрити прогалини тимчасовою огорожею, зробленою з дерев'яних стовпів. Дерев'яні стовпи будуть встановлені точно в тих місцях, де були/є відсутні/зламані бетонні стовпи. Однак, щоб зробити тимчасове відновлення швидшим і менш витратним, власники вирішили використовувати менше стовпів: дерев'яний стовп буде використовуватися для заміни відсутнього/зламаного бетонного стовпа лише в тому випадку, якщо довжина колючого дроту, необхідного для закриття відстані до наступного стовпа (дерев'яного або бетонного), перевищує чотири метри.
Враховуючи опис, які стовпи відсутні/зламані, ви повинні написати програму, щоб визначити найменшу кількість дерев'яних стовпів, необхідних для закриття всіх прогалин в огорожі, відповідно до рішення власників.
Кожен тестовий випадок описується за допомогою двох рядків. Перший рядок містить ціле число , що вказує кількість початкових бетонних стовпів в огорожі (5 \le N \le 5000). Другий рядок містить цілих чисел X_i, що вказують стан кожного бетонного стовпа після торнадо (0 \le X_i \le 1 для i = 1, 2, \ldots, N). Якщо X_i = 1, стовп в хорошому стані, якщо X_i = 0, стовп зламаний або відсутній. Зверніть увагу, що стовп X_N знаходиться поруч зі стовпом X_1.
Для кожного тестового випадку виведіть рядок з цілим числом, що представляє мінімальну кількість дерев'яних стовпів, які потрібні для відновлення огорожі, відповідно до рішення власників.
Приклад 1