Power Sequence

题意翻译

给定一个序列 $a_0,a_1......a_{n-1}$，你可以重排 $a$ 数组。需要你找出一个正整数 $c$，需满足 $\sum\limits_{i=0}^{n-1}|a_i-c^i|$ 最小，输出$\sum\limits_{i=0}^{n-1}|a_i-c^i|$。

题目描述

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.

输入输出格式

输入格式

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 $ ).

输出格式

Print the minimum cost to transform $ a_0, a_1, ..., a_{n-1} $ into a power sequence.

输入输出样例

输入样例 #1

3
1 3 2

输出样例 #1

1

输入样例 #2

3
1000000000 1000000000 1000000000

输出样例 #2

1999982505

说明

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