Курони очень зол на других авторов за использование его в качестве темы! В качестве наказания он заставил их решить следующую задачу:
У вас есть массив \(a\), состоящий из \(n\) целых положительных чисел. Операция состоит из выбора элемента и добавления к нему \(1\) или вычитания из него \(1\), чтобы элемент остался положительным. Назовем массив хорошим, если наибольший общий делитель всех его элементов не равен \(1\). Найдите минимальное количество операций, необходимых, чтобы сделать массив хорошим.
Не в силах сравниться с интеллектом Курони, авторы не смогли решить задачу. Помоги им сбежать от наказания Курони!
Выходные данные
Выведите одно целое число — минимальное количество операций, необходимых, чтобы сделать массив хорошим.
Примечание
В первом примере первый массив уже хороший, так как наибольший общий делитель всех элементов равен \(2\).
Во втором примере мы можем применить следующие операции:
- Добавьте \(1\) ко второму элементу, сделав его равным \(9\).
- Вычтите \(1\) из третьего элемента, сделав его равным \(6\).
- Добавьте \(1\) к пятому элементу, сделав его равным \(2\).
- Добавьте \(1\) к пятому элементу снова, сделав его равным \(3\).
Наибольший общий делитель всех элементов будет равен \(3\), поэтому массив будет хорошим. Можно показать, что никакая последовательность из трех или менее операций не может сделать массив хорошим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 2 4
|
0
|
|
2
|
5
9 8 7 3 1
|
4
|