Массив \(b\) называется хорошим, если сумма элементов \(b\) четная.
Вам дан массив \(a\) из \(n\) положительных целых чисел. За одну операцию вы можете выбрать индекс \(i\) и заменить \(a_i := \lfloor \frac{a_i}{2} \rfloor\). \(^\dagger\)
Найдите минимальное число операций (возможно, \(0\)), необходимое, чтобы сделать \(a\) хорошим. Можно показать, что всегда возможно сделать \(a\) хорошим.
\(^\dagger\) \(\lfloor x \rfloor\) обозначает округление вниз, то есть наибольшее число, меньшее или равное \(x\). Например, \(\lfloor 2.7 \rfloor = 2\), \(\lfloor \pi \rfloor = 3\) и \(\lfloor 5 \rfloor =5\).
Выходные данные
Для каждого набора входных данных выведите минимальное необходимое число операций для того, чтобы сделать \(a\) хорошим.
Примечание
В первом набора входных данных массив \(a\) хороший изначально.
Во втором наборе можно дважды выполнить операцию с индексом \(2\). После первой операции массив \(a\) становится равным \([7,2]\). После выполнения операции с индексом \(2\) снова массив \(a\) становится равным \([7,1]\), этот массив хороший. Можно показать, что невозможно сделать массив \(a\) хорошим за меньшее число операций.
В третьем примере \(a\) станет равным \([0,2,4]\), если мы выполним операцию один раз с индексом \(1\). Так как \([0,2,4]\) хороший, то ответ равен \(1\).
В четвертом примере нужно выполнить операцию с индексом \(1\) четыре раза. После всех операций \(a\) становится равным \([0]\). Можно показать, что невозможно сделать массив \(a\) хорошим за меньшее число операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
1 1 1 1
2
7 4
3
1 2 4
1
15
|
0
2
1
4
|