← 返回题目列表

Codeforces · 1188/D

D. 使相等

中文机器翻译题面 查看原题

给你 $$$n$$$ 数字 $$$a_1, a_2, \dots, a_n$$$。在一次操作中,我们可以将 $$$2$$$ 的非负整数幂添加到这些数字中的任何一个。

要使所有 $$$n$$$ 数字相等,我们需要执行的最少运算次数是多少?可以证明,在给定的约束下,它不会超过$$$10^{18}$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^{17}$$$)。

输出

准确输出一个整数——使所有 $$$n$$$ 数字相等所需执行的最少操作数。

示例

输入 #1

4
228 228 228 228

输出 #1

0

输入 #2

3
2 2 8

输出 #2

3

注意

在第一个示例中,所有数字已经相等。所以需要的操作次数是$$$0$$$。

在第二个示例中,我们可以应用运算 $$$3$$$ 次:将 $$$8$$$ 添加到第一个 $$$2$$$,将 $$$8$$$ 添加到第二个 $$$2$$$,将 $$$2$$$ 添加到 $$$8$$$,使所有数字等于 $$$10$$$。可以证明,在小于$$$3$$$的运算中,我们不能使所有数字相等。