304876: CF926B. Add Points

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Add Points

题意翻译

有一条数轴上有n个点。输入n和每个点的坐标,输出使每两个相邻点距离相同,最少要加入多少个点。 样例1解释:加入一个坐标为0的点,则$\text{0-(-5)=5-0=10-5=5}$,所以至少加入一个点。

题目描述

There are $ n $ points on a straight line, and the $ i $ -th point among them is located at $ x_{i} $ . All these coordinates are distinct. Determine the number $ m $ — the smallest number of points you should add on the line to make the distances between all neighboring points equal.

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 3<=n<=100000 $ ) — the number of points. The second line contains a sequence of integers $ x_{1},x_{2},...,x_{n} $ ( $ -10^{9}<=x_{i}<=10^{9} $ ) — the coordinates of the points. All these coordinates are distinct. The points can be given in an arbitrary order.

输出格式


Print a single integer $ m $ — the smallest number of points you should add on the line to make the distances between all neighboring points equal.

输入输出样例

输入样例 #1

3
-5 10 5

输出样例 #1

1

输入样例 #2

6
100 200 400 300 600 500

输出样例 #2

0

输入样例 #3

4
10 9 0 -1

输出样例 #3

8

说明

In the first example you can add one point with coordinate $ 0 $ . In the second example the distances between all neighboring points are already equal, so you shouldn't add anything.

Input

题意翻译

有一条数轴上有n个点。输入n和每个点的坐标,输出使每两个相邻点距离相同,最少要加入多少个点。 样例1解释:加入一个坐标为0的点,则$\text{0-(-5)=5-0=10-5=5}$,所以至少加入一个点。

加入题单

上一题 下一题 算法标签: