| Codeforces Round 612 (Div. 1) |
|---|
| Закончено |
Вадим очень любит наряжать новогоднюю ёлку, поэтому ему подарили невероятно красивую гирлянду. Она состоит из $$$n$$$ лампочек, расположенных в ряд. На каждой лампочке написано число от $$$1$$$ до $$$n$$$, причем все числа различны и шли в произвольном порядке. Пока Вадим решал задачи, его домашний Карась снял с гирлянды некоторые лампочки. Теперь Вадим хочет вернуть их на место.
Вадим хочет повесить все лампочки обратно на гирлянду. Он считает сложностью гирлянды количество пар соседних лампочек, на которых написаны числа разной четности (то есть имеющие разные остатки при делении на $$$2$$$). Например, сложность гирлянды 1 4 2 3 5 равна $$$2$$$, а сложность гирлянды 1 3 5 7 6 4 2, равна $$$1$$$.
Никто не любит сложности, поэтому Вадим хочет минимизировать количество таких пар. Найдите способ повесить снятые лампочки на гирлянду, чтобы минимизировать ее сложность.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество лампочек в гирлянде.
Вторая строка содержит $$$n$$$ целых чисел $$$p_1,\ p_2,\ \ldots,\ p_n$$$ ($$$0 \le p_i \le n$$$) — номер $$$i$$$-й лампочки или $$$0$$$, если Карась ее снял.
Выведите единственное число — минимальную сложность гирлянды.
5 0 5 0 2 3
2
7 1 0 0 5 0 0 2
1
В первом примере надо расставить лампочки как 1 5 4 2 3. В этом случае сложность будет равна 2, так как рядом расположены пары лампочек $$$(5, 4)$$$ и $$$(2, 3)$$$.
Во втором примере один из правильных ответов 1 7 3 5 6 4 2.
