Задан массив целых чисел \(a_1, a_2, \dots, a_n\), все его элементы различны.
Сначала вы вставляете в этот массив еще одно целое число \(a_{n+1}\). \(a_{n+1}\) не должно быть равно ни одному из \(a_1, a_2, \dots, a_n\).
Затем все элементы массива надо будет сделать равными. Для этого вы выбираете положительное целое число \(x\) (\(x > 0\)). После этого за одну операцию вы прибавляете \(x\) ровно к одному элементу массива. Обратите внимание, что \(x\) одинаковый для всех операций.
Какое наименьшее количество операций вам потребуется, чтобы сделать все элементы равными, после выбора \(a_{n+1}\) и \(x\)?
Выходные данные
На каждый набор входных данных выведите одно целое число — наименьшее количество операций, которое вам потребуется, чтобы сделать все элементы равными, после выбора целых чисел \(a_{n+1}\) и \(x\).
Примечание
В первом наборе входных данных вы можете выбрать \(a_{n+1} = 4\), массив станет \([1, 2, 3, 4]\). Затем вы можете выбрать \(x = 1\) и применить операцию \(3\) раза к первому элементу, \(2\) раза ко второму элементу, \(1\) раз к третьему элементу и \(0\) раз к четвертому элементу.
Во втором наборе вы можете выбрать \(a_{n+1} = 13, x = 4\).
В третьем наборе вы можете выбрать \(a_{n+1} = 9, x = 1\). Затем применить операцию один раз к \(a_{n+1}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 2 3
5
1 -19 17 -3 -15
1
10
|
6
27
1
|