Задача I. I really want to fix lamps

Автор:Денис Лысенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

В Найт-Сити близится Новогодняя пора. Власти города на последние деньги в этом году восстановили городское освещение в жилых районах из n фонарей нового класса. Модель уличного фонаря с выдвижной голограммой новогодней ели для понижения излишнего стресса у горожан. Каждый фонарь имеет нумерацию согласно их яркости от 1 до n, причем вся нумерация на фонарях идёт в произвольном порядке.

Но разве киберпанкам есть дело до такой мелочи? Конечно есть, при свете преступления заметнее. Поэтому несколько банд наемников оперативно перебили только что восстановленное освещение в нескольких точках города.

Теперь городскому аппарату придется занимать средства у Арасаки для восстановления сети освещения. Мегакорпорация также поделилась с властями города информацией, что некоторая комбинация фонарей вызывает у некоторых людей короткое замыкание зрительных имплантов, поэтому деньги будут выданы в займы, если будут соблюдаться некоторые условия расположения фонарей.

Арасака называет причину воникновения короткого замыкания в зрительных имплантах - рядом стоящие фонари, имеющие разную чётность яркости освещения. Также мегакорпорация называет такую пару фонарей замыкающими.

Арасака прогнозирует, что избегание замыкающих фонарей перестанет так сильно выводить из себя уличный сброд, поэтому власти города хотят минимизировать количество замыкающих пар фонарей, чтобы их потом снова не разбили.

Найдите способ восстановить уничтоженные фонари на улицах, чтобы минимизировать количество замыкающих фонарей.

Формат входных данных

Первая строка содержит одно целое число n (1 ≤ n ≤ 100) — количество фонарей на улице.

Вторая строка содержит n целых чисел a1, a2, ..., an (0 ≤ ai ≤ n) — яркость i-го фонаря или 0, если киберпанки его уничтожили.

Формат выходных данных

Выведите единственное число — минимальную сложность правильного освещения.

Ограничения

(1 ≤ n ≤ 100)

(0 ≤ ai ≤ n)

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения
n
1101 ≤ n ≤ 10
2351 ≤ n ≤ 50
3551 ≤ n ≤ 100

Пояснение к примерам

В примере один из способов оптимального размещения фонарей выглядит следующим образом - 1 3 5 4 2 6. Ответ 1 пара замыкающих фонарей.

Примеры тестов

Стандартный вход Стандартный выход
1
6
1 0 0 4 0 0
1

0.076s 0.011s 13