如果存在正整数 $$$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\}$$$。