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

N = int(input())
a = list(map(int,input().split()))
a.sort()
c = 1
l= int(a[N-1]**(1/(N-1)))
r= l+1

scorel = 0
for i in range(N):
    scorel += abs(a[i]-l**i)

scorer = 0
for i in range(N):
    if r**i > 10**15:
        break
    scorer += abs(a[i]-r**i)

print(min(scorer,scorel))
