Вадим очень любит наряжать новогоднюю ёлку, поэтому ему подарили невероятно красивую гирлянду. Она состоит из \(n\) лампочек, расположенных в ряд. На каждой лампочке написано число от \(1\) до \(n\), причем все числа различны и шли в произвольном порядке. Пока Вадим решал задачи, его домашний Карась снял с гирлянды некоторые лампочки. Теперь Вадим хочет вернуть их на место.
Вадим хочет повесить все лампочки обратно на гирлянду. Он считает сложностью гирлянды количество пар соседних лампочек, на которых написаны числа разной четности (то есть имеющие разные остатки при делении на \(2\)). Например, сложность гирлянды 1 4 2 3 5 равна \(2\), а сложность гирлянды 1 3 5 7 6 4 2, равна \(1\).
Никто не любит сложности, поэтому Вадим хочет минимизировать количество таких пар. Найдите способ повесить снятые лампочки на гирлянду, чтобы минимизировать ее сложность.
Выходные данные
Выведите единственное число — минимальную сложность гирлянды.
Примечание
В первом примере надо расставить лампочки как 1 5 4 2 3. В этом случае сложность будет равна 2, так как рядом расположены пары лампочек \((5, 4)\) и \((2, 3)\).
Во втором примере один из правильных ответов 1 7 3 5 6 4 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
0 5 0 2 3
|
2
|
|
2
|
7
1 0 0 5 0 0 2
|
1
|