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