Массив \(a\) называется хорошим, если для любой пары соседних элементов \(a_i\) и \(a_{i+1}\) (\(1\le i \lt n\)) имеют разную четность. В частности, массив размера \(1\) всегда является хорошим.
Вам задан массив длины \(n\).
За одну операцию можно выбрать любую пару соседних элементов, в которой элементы имеют одинаковую четность, удалить их, а затем вставить на то же место их произведение.
Определите минимальное число операций, необходимое для того, чтобы сделать массив хорошим.
Выходные данные
Для каждого набора входных данных выведите число, равное минимальному числу операций, необходимых для получения хорошего массива.
Примечание
Рассмотрим первый набор входных данных. Выберем \(2\)-е и \(3\)-е числа и применим операций к ним. Массив, до этого равный \([1, \color{red}{7}, \color{red}{11}, 2, 13]\), станет равен \([1, \color{red}{77}, 2, 13]\). Затем выберем \(1\)-й и \(2\)-й элементы. Массив, равный \([\color{red}{1}, \color{red}{77}, 2, 13]\), станет равен \([\color{red}{77}, 2, 13]\). Таким образом, нам достаточно \(2\) операций. Можно доказать, что меньшим числом операций обойтись нельзя.
Во втором наборе входных данных данный массив уже является хорошим. Поэтому нам нужно всего \(0\) операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
1 7 11 2 13
4
1 2 3 4
6
1 1 1 2 2 3
|
2
0
3
|