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

Difficulty: interview

Starter code:

Solutions:


n=int(input())
a=list(map(int,input().split()))
a=sorted(a)

if(n>65):
	print(sum(a)-n)
elif(n==1 or n==2):
	print(a[0]-1)
else:
	ans=10**20

	for i in range(1,50000):
		now=1
		ta=0
		for j in a:
			ta+=abs(now-j)
			now*=i
		ans=min(ans,ta)

	print(ans)


n = int(input())
b = list(map(int, input().split()))
b.sort()
ans = float("inf")
j = 1
while (j ** (n - 1) <= 10 ** 10):
    s = 0
    for p in range(n):
        s += abs(j ** p - b[p])
    ans = min(ans, s)
    j += 1
print(ans)












































n = int(input())
arr = sorted(list(map(int, input().split())))

ans = sum(arr) - n

for i in range(2, 10 ** 9):
    if abs(i ** (n - 1) - arr[-1]) > ans:
        break

    ans2 = 0
    for j in range(0, n):
        ans2 += abs(i ** j - arr[j])

    ans = min(ans, ans2)

print(ans)


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



n = val()
l = sorted(li())
if n <= 36:
    ans = float('inf')
    for i in range(1, 10 ** 5):
        curr = 0
        for j in range(n):
            curr += abs(l[j] - i ** j)
            if i ** j > 10 ** 10:
                curr = float('inf')
                break
        ans = min(ans, curr)
else:
    ans = 0
    for j in l:
        ans += abs(j - 1)
print(ans)

n = int(input())
b = list(map(int,input().split()))
b.sort()
val = b[-1]**(1/(n-1))
pos1 = int(val)
pos2 = int(val) + 1
val1 = 0
val2 = 0
for i in range(n):
	val1 += abs(b[i]-(pos1**i))
	val2 += abs(b[i]-(pos2**i))
print(min(val1,val2))


import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(lst):  # fix inputs here
    lst = sorted(lst)
    console("----- solving ------")
    console(lst)

    if len(lst) > 40:
        return sum(lst) - len(lst)   

    base = 0
    minres = 10**11
    while base**len(lst) < (10**15):
        req = [base**i for i in range(len(lst))]
        diff = [abs(r-x) for r,x in zip(req, lst)]
        # console(req, base, diff, sum(diff))
        minres = min(minres, sum(diff))
        base += 1

    return minres


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# sys.stdin.readlines()

# for case_num in range(int(input())):
for _ in range(1):
    # read line as a string
    # strr = input()

    # read line as an integer
    _ = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for _ in range(nrows):
    #     grid.append(list(map(int,input().split())))

    res = solve(lst)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)


n = int(input())
an = list(sorted(map(int, input().split())))

ans = sum(an)-n
for i in range(2, 10**5):
    newa = 0
    for j in range(n):
        newa += abs(an[j]-i**j)
        if newa >= ans:
            break
    if newa < ans:
        ans = newa

print(ans)


N = int(input())
arr = [int(x) for x in input().split()]
arr = sorted(arr)
MAX_NUM = 1e18

ans = 1e18
for i in range(1,32000):
	curr = 0
	num = 1
	for j in range(N):
		curr += abs(arr[j]-num)
		num *= i
		if curr > MAX_NUM:
			break
	if curr > MAX_NUM:
		break
	ans = min(ans, curr)

print(ans)

n = int(input())
arr = [*map(int, input().split())]

arr.sort()
x = int(arr[-1] ** (1 / (n - 1)))
y = x + 1
ans = res = 0

for i, j in zip(arr, range(n)):
	ans += abs(i - (x ** j))
	res += abs(i - (y ** j))

print(min(ans, res))

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

            
n = int(input())

arry = list(map(int,input().split()))

maxNum = max(arry)

maxRecur = maxNum ** (1/(n-1))

currMin=float("inf")
#print(maxRecur)
arry.sort()
for i in range(int(maxRecur)+2):
    curr = 0
    for j in range(n):
        #print(i**j)
        curr += abs(i**j-arry[j])
    #print(i,curr)
    currMin = min(currMin,curr)
print(currMin)



n=int(input())
l=list(map(int,input().split()))
l.sort()
cost=sum([i-1 for i in l])
c=2
con=True
while con:
    tmp=0
    cc=1
    for i in range(n):
        tmp+=abs(l[i]-cc)
        if cost<tmp: 
            con=False
            break
        cc*=c
    if con: cost=tmp
    c+=1

print(cost)

from collections import Counter
import math
n=int(input())
l=list(map(int,input().split()))
l.sort()
m=l[-1]
p=m**(1/(n-1))
ans=math.ceil(p)
ans1=int(p)
c1=0
c2=0
for i in range(n):
    if((ans**i)!=l[i]):
        c1+=abs((ans**i)-l[i])
for i in range(n):
    if((ans1**i)!=l[i]):
        c2+=abs((ans1**i)-l[i])
print(min(c1,c2))

n=int(input())
a=list(map(int,input().split()))

a.sort()
shita=int(a[-1]**(1/(n-1)))
ue=shita+1

sumshita=0
sumue=0

for i in range(n):
    targetshita=shita**i
    sumshita+=abs(targetshita-a[i])
    targetue=ue**i
    sumue+=abs(targetue-a[i])

print(min(sumshita,sumue))

n=int(input())
a=list(map(int,input().split()))
def f(x):
    p=1
    re=0
    for i in range(n):
        re+=abs(p-a[i])
        p*=x
    return re
def g():
    re=0
    for i in range(n):
        re+=a[i]-1
    return re
a.sort()
if n>32:
    print(g())
    return
i=1
ans=10**18
while 1:
    tmp=f(i)
    if ans<tmp: break
    ans=tmp
    i+=1
print(ans)


from math import log10
N = int(input())
l = list(map(int,input().split()))
l.sort()
x = round(pow(10,log10(l[-1])/(N-1)))
minm = pow(10,15)
for b in range(max(1,x-3),x+2):
    n = 0
    for i in range(N):
        n += abs(pow(b,i) - l[i])
    minm = min(minm,n)
print(minm)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = int(a[-1] ** (1 / (n - 1)))
print(min(sum(abs(pow(ans, i) - a[i]) for i in range(n)), sum(abs(pow(ans + 1, i) - a[i]) for i in range(n))))

n=int(input())
arr=list(map(int,input().split()))
arr.sort()
m=0
for i in arr:
    m+=abs(i-1)
c=2
if n>10:
    while c<20:
        t=0
        for i in range(n):
            t+=abs(c**i-arr[i])
            if t>=m:
                break
        if t<m:
            m=t
        c+=1
    print(m)
else:
    while c<=1000000:
        t=0
        for i in range(n):
            t+=abs(c**i-arr[i])
            if t>=m:
                break
        if t<m:
            m=t
        c+=1
    print(m)


def solve(arr):
    arr.sort()
    c = 2
    ans = sum(v - 1 for v in arr)
    while True:
        cur = 1
        cur_ans = 0
        for v in arr:
            if cur - arr[-1] > ans:
                return ans
            cur_ans += abs(v - cur)
            cur *= c
        ans = min(ans, cur_ans)

        c += 1


n = int(input())
*arr, = list(map(int, input().split()))
print(solve(arr))


"""
NTC here
"""


def iin(): return int(input())


def lin(): return list(map(int, input().split()))


def main():
    T = 1
    for t in range(T):
        n = iin()
        a = lin()
        a.sort()
        ans = sum(a)-n
        for val in range(1, 100001):
            sm = 0
            ch = 1
            br = 0
            for i in a:
                sm += abs(ch-i)
                ch *= val
                if sm>ans:
                    br = 1
                    break
            else:
                # print(ans, sm, val)
                ans = min(ans, sm)
            if br:break
        print(ans)



main()

"""
3
4 1 3 1
4 4 4 3
5 3 3 2
"""