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

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.

-----Examples-----

Input 3 1 3 2

Output 1

Input 3 1000000000 1000000000 1000000000

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