| Автор: | Денис Лысенко | Ограничение времени: | 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 | |||
| 1 | 10 | 1 ≤ n ≤ 10 | |
| 2 | 35 | 1 ≤ n ≤ 50 | |
| 3 | 55 | 1 ≤ n ≤ 100 | |
В примере один из способов оптимального размещения фонарей выглядит следующим образом - 1 3 5 4 2 6. Ответ 1 пара замыкающих фонарей.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|