1397_B. 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\}.
```python
import math, sys
from collections import defaultdict, Counter, deque
 
INF = float('inf')
MOD = 10 ** 9 + 7
 
def gcd(a, b):
	while b:
		a, b = b, a%b
	return a
 
def isPrime(n):
	if (n <= 1): 
		return False
	i = 2
	while i ** 2 <= n:
		if n % i == 0:
			return False
		i += 1
	return True
 
def primeFactors(n):
	factors = defaultdict(int)
	i = 2
	while i ** 2 <= n:
		while n % i == 0:
			factors[i] += 1
			n //= i 
		i += 1
	if n > 1:
		factors[n] += 1 
	return factors
 
def vars():
	return map(int, input().split())
 
def array():
	return list(map(int, input().split()))


def a():
	n = int(input())
	m = defaultdict(int)

	for i in range(n):
		s = input()
		for c in s:
			m[c] += 1 

	res = 'YES'
	for c in m:
		if m[c] % n != 0:
			res = 'NO'
			break
	print(res)

def b():
	n = int(input())
	arr = array()

	arr.sort()

	maxi = arr[-1]

	res1 = math.floor(maxi ** (1 / (n - 1)))
	res2 = math.ceil(maxi ** (1 / (n - 1)))

	ans1 = ans2 = 0

	for i in range(n):
		ans1 += abs(arr[i] - (res1 ** i))

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

	print(min(ans1, ans2))

if __name__ == "__main__":
	t = 1
	# t = int(input())
	for _ in range(t):
		b()

```