407778: GYM102892 7 Trailing Zeros

You have an array $$$a$$$ consisting of $$$n$$$ positive integers. Based on this array, you're trying to calculate the product of $$$a_i^i$$$ for all values of $$$i$$$ from $$$1$$$ to $$$n$$$. For example, this value for the array $$$a = [5, 3, 4, 7, 2]$$$ is equal to $$$5^1 * 3^2 * 4^3 * 7^4 * 2^5 = 221276160$$$. We'll call this the cumulative product value.

You're goal is for this value to have the minimum number of trailing zeros in its binary representation. For example, 16 has four trailing zeros in its binary representation, while 34 only has one trailing zero.

To accomplish this, you're going to perform a certain number of swaps of adjacent elements in this array. Your task is to calculate the minimum number of swaps needed in order to obtain the minimum possible amount of trailing zeros in the binary representation of the cumulative product value, across all permutations of the array.

The first line of input contains a single positive integer $$$n$$$ $$$(1 <= n <= 10^5)$$$: the length of the array.

The next line contains $$$n$$$ space-separated integers: the array $$$(1 <= a_i <= 10^9)$$$.

Output a single positive integer: the minimum number of swaps between adjacent elements in the array, in order to minimize the cumulative product value.

Full problem: 38 points

4
3 16 2 4

4

In the example, the array $$$b = [16, 4, 2, 3]$$$ has the minimum number of trailing zeros in its cumulative product value, across all permutations of $$$a$$$.