← 返回题目列表

Codeforces · 1397/B

B. 电源顺序

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

如果存在正整数 $$$c$$$,我们将正整数列表 $$$a_0, a_1, ..., a_{n-1}$$$ 称为幂序列,因此对于每个 $$$0 \le i \le n-1$$$ 则 $$$a_i = c^i$$$。

给定 $$$n$$$ 正整数 $$$a_0, a_1, ..., a_{n-1}$$$ 列表,您可以:

- 重新排序列表(即选择 $$$\{0,1,...,n - 1\}$$$ 的排列 $$$p$$$ 并将 $$$a_i$$$ 更改为 $$$a_{p_i}$$$),然后
- 执行以下操作任意多次:选择一个索引 $$$i$$$ 并将 $$$a_i$$$ 更改为 $$$a_i - 1$$$ 或 $$$a_i + 1$$$(即将 $$$a_i$$$ 增加或减少 $$$1$$$),成本为 $$$1$$$。

找出将 $$$a_0, a_1, ..., a_{n-1}$$$ 转换为幂序列的最小成本。

输入

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

第二行包含 $$$n$$$ 整数 $$$a_0, a_1, ..., a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$)。

输出

打印将 $$$a_0, a_1, ..., a_{n-1}$$$ 转换为幂序列的最小成本。

示例

输入 #1

3
1 3 2

输出 #1

1

输入 #2

3
1000000000 1000000000 1000000000

输出 #2

1999982505

注意

在第一个示例中,我们首先将 $$$\{1, 3, 2\}$$$ 重新排序为 $$$\{1, 2, 3\}$$$,然后将 $$$a_2$$$ 增加到 $$$4$$$,成本 $$$1$$$ 以获得幂序列 $$$\{1, 2, 4\}$$$。