F. Курони и наказание
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Курони очень зол на других авторов за использование его в качестве темы! В качестве наказания он заставил их решить следующую задачу:

У вас есть массив $$$a$$$, состоящий из $$$n$$$ целых положительных чисел. Операция состоит из выбора элемента и добавления к нему $$$1$$$ или вычитания из него $$$1$$$, чтобы элемент остался положительным. Назовем массив хорошим, если наибольший общий делитель всех его элементов не равен $$$1$$$. Найдите минимальное количество операций, необходимых, чтобы сделать массив хорошим.

Не в силах сравниться с интеллектом Курони, авторы не смогли решить задачу. Помоги им сбежать от наказания Курони!

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

Первая строка содержит единственное целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)  — количество чисел в массиве.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$. ($$$1 \le a_i \le 10^{12}$$$)  — элементы массива.

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

Выведите одно целое число  — минимальное количество операций, необходимых, чтобы сделать массив хорошим.

Примеры
Входные данные
3
6 2 4
Выходные данные
0
Входные данные
5
9 8 7 3 1
Выходные данные
4
Примечание

В первом примере первый массив уже хороший, так как наибольший общий делитель всех элементов равен $$$2$$$.

Во втором примере мы можем применить следующие операции:

  • Добавьте $$$1$$$ ко второму элементу, сделав его равным $$$9$$$.
  • Вычтите $$$1$$$ из третьего элемента, сделав его равным $$$6$$$.
  • Добавьте $$$1$$$ к пятому элементу, сделав его равным $$$2$$$.
  • Добавьте $$$1$$$ к пятому элементу снова, сделав его равным $$$3$$$.

Наибольший общий делитель всех элементов будет равен $$$3$$$, поэтому массив будет хорошим. Можно показать, что никакая последовательность из трех или менее операций не может сделать массив хорошим.