1397B · Power Sequence

Problem: 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.

Input Format: 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$).

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

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