Preparing for battle#9083
The distinguished Marshal La Hsram considers the best fighting unit to be a squad arranged in two ranks of equal size, led by a commander. Therefore, each unit must consist of an odd number of warriors. However, sometimes, units with an even number of soldiers are present. In that case, the marshal personally calls all detachments with a certain even number of fighters to the parade ground in order to perform division operations. After his commands are executed, these units are divided into two equal parts: one remains in his army, and the other is transferred to the reserve. These operations are repeated until all units have an odd number of soldiers.
Determine the minimum number of operations required for the marshal to achieve the desired composition of units.
For example, if the initial composition of the units is: [22, 31, 52, 13, 26, 11, 26], the marshal may:
Take units with q = 22 soldiers, divide them to get [11, 31, 52, 13, 26, 11, 26];
Then take q = 52, resulting in [11, 31, 26, 13, 26, 11, 26];
Finally, with q = 26: [11, 31, 13, 13, 13, 11, 13].
Thus, the reorganization is completed in three steps.
The input contains a single integer (5 \le N \le 10^6) — the number of units. The next line contains positive integers a_1, a_2, \ldots, a_N (11 \le a_i \le 10^9) — the sizes of the units.
Print a single integer: the minimum number of division operations needed to achieve the desired composition.
Example 1