На прямой находится n точек, причем i-я точка имеет координату xi. Координаты всех точек различны.
Определите число m — минимальное количество точек, которые нужно добавить на прямую так, чтобы расстояния между каждой парой соседних точек на прямой были одинаковыми.
Выходные данные
Выведите число m — минимальное количество точек, которые нужно добавить на прямую так, чтобы расстояния между каждой парой соседних точек на прямой были одинаковыми.
Примечание
В первом примере достаточно добавить одну точку с координатой 0.
Во втором примере расстояния между всеми парами начальных точек равны между собой, поэтому ничего добавлять не нужно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
-5 10 5
|
1
|
|
2
|
6
100 200 400 300 600 500
|
0
|
|
3
|
4
10 9 0 -1
|
8
|