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

На прямой находится n точек, причем i-я точка имеет координату xi. Координаты всех точек различны.

Определите число m — минимальное количество точек, которые нужно добавить на прямую так, чтобы расстояния между каждой парой соседних точек на прямой были одинаковыми.

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

В первой строке следует целое число n (3 ≤ n ≤ 100 000) — количество точек.

Во второй строке следует последовательность целых чисел x1, x2, ..., xn ( - 109 ≤ xi ≤ 109) — координаты точек. Координаты всех точек различны. Точки могут следовать в любом порядке.

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

Выведите число m — минимальное количество точек, которые нужно добавить на прямую так, чтобы расстояния между каждой парой соседних точек на прямой были одинаковыми.

Примеры
Входные данные
3
-5 10 5
Выходные данные
1
Входные данные
6
100 200 400 300 600 500
Выходные данные
0
Входные данные
4
10 9 0 -1
Выходные данные
8
Примечание

В первом примере достаточно добавить одну точку с координатой 0.

Во втором примере расстояния между всеми парами начальных точек равны между собой, поэтому ничего добавлять не нужно.