思路

统计 c0 为偶数的数量，c1 为奇数的数量，m = n / 2

• c0 == c1，答案为 0
• c0 < c1，选择 (c1 - m) 个奇数均进行一次乘2操作变成偶数，任选 (c1 - m) 个奇数即可
• c0 > c1，选择 (c0 - m) 个偶数进行下取整除法变成奇数，一定可以变成奇数，最差就是变成 1 选择哪些偶数进行下取整呢？ 就是下取整除法从偶数变成奇数的最小次数的前 (c0 - m) 个偶数即可

时间复杂度：$O(n\log n)$

问题描述

小红是一位资深的程序员,他最近在研究一种特殊的数组操作。他有一个由正整数组成的数组,数组的长度是偶数。小红可以对数组中的任意一个数字执行以下两种操作之一:

1. 将该数字乘以 $2$;
2. 将该数字除以 $2$ 并向下取整。

小红的目标是通过一系列操作,使得最终数组中恰好一半的数字是奇数,另一半是偶数。他希望找到一种方案,使得操作次数最少。

输入格式

输入的第一行包含一个正偶整数 $n$,表示数组的长度。

第二行包含 $n$ 个正整数 $A_1, A_2, \ldots, A_n$,表示初始的数组。

输出格式

输出一个整数,表示达成目标所需的最少操作次数。

样例输入

6
1 1 4 5 1 4

样例输出

1

样例解释

初始数组为 $[1, 1, 4, 5, 1, 4]$。将第四个数字 $5$ 除以 $2$ 并向下取整,得到 $[1, 1, 4, 2, 1, 4]$,此时数组中恰好一半是奇数,另一半是偶数。

评测数据与规模

对于所有评测用例,满足 $2 \leq n \leq 10^5, 1 \leq A_i \leq 10^9$,并且 $n$ 是偶数。