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
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$.
## Input
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
Output a single positive integer: the minimum number of swaps between adjacent elements in the array, in order to minimize the cumulative product value.
[samples]
## Scoring
Full problem: 38 points
## Note
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$.
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the array.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers.
For a permutation $ \sigma \in S_n $, define the **cumulative product value**:
$$
P(\sigma) = \prod_{i=1}^n a_{\sigma(i)}^i
$$
Let $ v_2(x) $ denote the 2-adic valuation of $ x \in \mathbb{Z}^+ $, i.e., the exponent of the highest power of 2 dividing $ x $.
**Objective**
Minimize $ v_2(P(\sigma)) $ over all permutations $ \sigma \in S_n $, and find the **minimum number of adjacent swaps** required to transform the original array $ A $ into a permutation $ \sigma^* $ achieving this minimum.
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ 1 \le a_i \le 10^9 $ for all $ i $
**Key Insight**
The 2-adic valuation of the cumulative product is:
$$
v_2(P(\sigma)) = \sum_{i=1}^n i \cdot v_2(a_{\sigma(i)})
$$
To minimize this sum, assign elements with **higher** $ v_2(a_j) $ to **smaller** indices $ i $, since the weight $ i $ is smaller.
Thus, the optimal permutation $ \sigma^* $ sorts elements by $ v_2(a_j) $ in **descending order** (i.e., highest power of 2 first).
**Objective (Rephrased)**
Compute the minimum number of adjacent swaps needed to sort the array according to the key $ v_2(a_i) $ in descending order (i.e., inversion count relative to this target ordering).