B. Степенная последовательность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем последовательность положительных чисел $$$a_0, a_1, ..., a_{n-1}$$$ степенной последовательностью, если найдется такое положительное целое число $$$c$$$, что для всех $$$0 \le i \le n-1$$$, $$$a_i = c^i$$$.

Вам дана последовательность из $$$n$$$ положительных чисел $$$a_0, a_1, ..., a_{n-1}$$$, вам разрешается:

  • Переупорядочить последовательность (иначе говоря, выбрать перестановку $$$p$$$ из $$$\{0,1,...,n - 1\}$$$ и заменить $$$a_i$$$ на $$$a_{p_i}$$$), и затем
  • Выполнить следующую операцию любое количество раз: выбрать индекс $$$i$$$ и заменить $$$a_i$$$ на $$$a_i - 1$$$ или $$$a_i + 1$$$ (иначе говоря, уменьшить или увеличить $$$a_i$$$ на $$$1$$$) за стоимость $$$1$$$.

Найдите минимальную стоимость, необходимую для превращения $$$a_0, a_1, ..., a_{n-1}$$$ в степенную последовательность.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$3 \le n \le 10^5$$$).

Во второй строке записаны $$$n$$$ целых чисел $$$a_0, a_1, ..., a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$).

Выходные данные

Выведите минимальную стоимость, необходимую для превращения $$$a_0, a_1, ..., a_{n-1}$$$ в степенную последовательность.

Примеры
Входные данные
3
1 3 2
Выходные данные
1
Входные данные
3
1000000000 1000000000 1000000000
Выходные данные
1999982505
Примечание

В первом примере сначала можно переупорядочить $$$\{1, 3, 2\}$$$ в $$$\{1, 2, 3\}$$$, затем увеличить $$$a_2$$$ до $$$4$$$ за стоимость $$$1$$$, чтобы получить степенную последовательность $$$\{1, 2, 4\}$$$.