CF1397B.Power Sequence

Let's call a list of positive integers $a_0, a_1, ..., a_{n-1}$ a power sequence if there is a positive integer $c$, so that for every $0 \le i \le n-1$ then $a_i = c^i$.

Given a list of $n$ positive integers $a_0, a_1, ..., a_{n-1}$, you are allowed to:

• Reorder the list (i.e. pick a permutation $p$ of ${0,1,...,n - 1}$ and change $a_i$ to $a_{p_i}$), then
• Do the following operation any number of times: pick an index $i$ and change $a_i$ to $a_i - 1$ or $a_i + 1$ (i.e. increment or decrement $a_i$ by $1$) with a cost of $1$.

Find the minimum cost to transform $a_0, a_1, ..., a_{n-1}$ into a power sequence.

我们称一个正整数序列 $a_0, a_1, ..., a_{n-1}$ 为幂序列，当且仅当存在某个正整数 $c$，使得对每个 $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$），每次操作代价为 $1$。

求将序列 $a_0, a_1, ..., a_{n-1}$ 变为一个幂序列所需的最小总代价。

The first line contains an integer $n$ ($3 \le n \le 10^5$).

The second line contains $n$ integers $a_0, a_1, ..., a_{n-1}$ ($1 \le a_i \le 10^9$).

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

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

Print the minimum cost to transform $a_0, a_1, ..., a_{n-1}$ into a power sequence.

输出将 $a_0, a_1, ..., a_{n-1}$ 变为幂序列的最小代价。

In the first example, we first reorder ${1, 3, 2}$ into ${1, 2, 3}$, then increment $a_2$ to $4$ with cost $1$ to get a power sequence ${1, 2, 4}$.

在第一个例子中，我们首先将 $\{1, 3, 2\}$ 重排为 $\{1, 2, 3\}$，然后以代价 $1$ 将 $a_2$ 增加至 $4$，从而得到一个幂序列 $\{1, 2, 4\}$。