Чтобы развить у юного Кевина арифметические навыки, его мать придумала следующую задачу.
Даны \(n\) целых чисел \(a_1, a_2, \ldots, a_n\), а также число \(s\), изначально равное \(0\). Кевин выполняет следующую операцию для \(i = 1, 2, \ldots, n\) по порядку:
- Добавить \(a_i\) к \(s\). Если полученное \(s\) чётное, Кевин зарабатывает очко, а затем делит \(s\) на \(2\) до тех пор, пока оно не станет нечётным.
Обратите внимание, что Кевин может заработать не более одного очка за операцию, даже если он сделал больше одного деления.
Поскольку операции деления считаются наиболее полезными для развития Кевина, его мать хочет переставить элементы \(a\) таким образом, чтобы общее количество баллов у Кевина было максимальным. Определите максимально возможное количество баллов.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество баллов.
Примечание
В первом наборе входных данных единственной перестановкой элементов \(a\) является \([1]\). \(s\) будет равен \(1\), а Кевин не заработает очков.
Во втором наборе входных данных единственным оптимальным расположением элементов \(a\) является \([2, 1]\). После операций \(s\) последовательно становится равным \(1\) и \(1\). Кевин зарабатывает по очку в обеих операциях.
В третьем наборе входных данных одной из оптимальных перестановок элементов \(a\) является \([2, 4, 6]\). После выполнения операций \(s\) последовательно становится равным \(1\), \(5\) и \(11\). Кевин заработает очко только на первой операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
1
2
1 2
3
2 4 6
4
1000000000 999999999 999999998 999999997
10
3 1 4 1 5 9 2 6 5 3
|
0
2
1
3
8
|