Торнадо!
Является ли эта необычная погода результатом постоянного вмешательства человека в природу? Или это просто часть естественного климатического цикла, который происходит на протяжении веков? Никто не может сказать наверняка, но факт остается фактом: природные явления, такие как торнадо и ураганы, обрушиваются на нашу страну с большей силой и частотой, чем в предыдущие десятилетия.
Недавно торнадо обрушилось на ферму Сильверадо, где разводят скот и производят молоко, нанеся значительный ущерб. Крыша сарая была сорвана, несколько деревьев выкорчеваны, фермерский грузовик перевернут... Но самое серьезное — это то, что торнадо разрушило несколько участков забора, окружавшего владение. Забор был тщательно построен: бетонные столбы располагались каждые два метра, а колючая проволока ограждала весь периметр фермы (периметр в метрах является четным числом, что делает забор идеально регулярным).
Теперь несколько столбов сломаны или отсутствуют, и в заборе образовались пробелы. Чтобы предотвратить выход скота за пределы владения, забор необходимо восстановить как можно быстрее. Полное восстановление забора с бетонными столбами займет много времени. Поэтому владельцы фермы решили временно закрыть пробелы деревянными столбами. Деревянные столбы будут установлены точно на тех местах, где отсутствуют или были сломаны бетонные столбы. Однако, чтобы сделать временное восстановление быстрее и дешевле, владельцы решили использовать меньше столбов: деревянный столб будет установлен только в том случае, если длина колючей проволоки, необходимой для закрытия расстояния до следующего столба (деревянного или бетонного), превышает четыре метра.
Учитывая описание того, какие столбы отсутствуют или сломаны, вы должны написать программу, чтобы определить минимальное количество деревянных столбов, необходимых для закрытия всех пробелов в заборе, согласно решению владельцев.
Входные данные
Каждый тестовый случай описывается двумя строками. Первая строка содержит целое число 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.
Выходные данные
Для каждого тестового случая выведите строку с целым числом, представляющим минимальное количество деревянных столбов, необходимых для восстановления забора, согласно решению владельцев.