#226. 守护神兽的修炼计划II

守护神兽的修炼计划II

在一个神秘的修仙大陆中,有一群神兽正在进行力量比拼。你的目标是让所有神兽的力量值达到平衡,为此你需要对它们的力量值进行调整。

每只神兽的初始力量值分别为 a1,a2,,ana_1, a_2, \dots, a_n。为了让所有神兽的力量值相等,你可以进行以下两种操作:

  1. 提升力量值: 选择一只神兽,将其力量值翻倍,即将 aia_i 变为 2×ai2 \times a_i
  2. 削弱力量值: 选择一只神兽,将其力量值减半(整数除法),即将 aia_i 变为 ai2\lfloor \frac{a_i}{2} \rfloor

你的目标是通过最少的操作次数,使所有神兽的力量值相等。

输入描述

  • 第一行包含一个整数 nn (1n1051 \leq n \leq 10^5),表示神兽的数量。
  • 第二行包含 nn 个正整数 a1,a2,,ana_1, a_2, \dots, a_n (1ai1051 \leq a_i \leq 10^5),表示每只神兽的初始力量值。

输出描述

输出一个整数,表示让所有神兽力量值相等所需的最少操作次数。

样例

3
4 8 2
2
3
3 5 6
5

解释

对于第一个样例,初始力量值为 [4,8,2][4, 8, 2]。通过以下两次操作,可以将所有神兽的力量值调整为 44

  1. 对第二只神兽的力量值减半:[4,4,2][4, 4, 2]
  2. 对第三只神兽的力量值翻倍:[4,4,4][4, 4, 4]

因此最少需要 22 次操作。