Power Sequence
Description
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.
Input
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
Print the minimum cost to transform $a_0, a_1, ..., a_{n-1}$ into a power sequence.
Samples
3
1 3 2
1
3
1000000000 1000000000 1000000000
1999982505
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\}$.