A13747. 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.

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$ ).

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

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\}$ .