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 ≤ i ≤ 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 ≤ n ≤ 10^5).

The second line contains n integers a_0, a_1, ..., a_{n-1} (1 ≤ a_i ≤ 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}.

inputFormat

Input

The first line contains an integer n (3 ≤ n ≤ 10^5).

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

outputFormat

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

样例

3
1 3 2

1

</p>