Назовем последовательность положительных чисел \(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}\) в степенную последовательность.
Выходные данные
Выведите минимальную стоимость, необходимую для превращения \(a_0, a_1, ..., a_{n-1}\) в степенную последовательность.
Примечание
В первом примере сначала можно переупорядочить \(\{1, 3, 2\}\) в \(\{1, 2, 3\}\), затем увеличить \(a_2\) до \(4\) за стоимость \(1\), чтобы получить степенную последовательность \(\{1, 2, 4\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 3 2
|
1
|
|
2
|
3
1000000000 1000000000 1000000000
|
1999982505
|