← 返回题目列表

Codeforces · 926/B

B. 添加积分

中文机器翻译题面 查看原题

直线上有n个点,其中第i个点位于xi。所有这些坐标都是不同的。

确定数字 m — 为使所有相邻点之间的距离相等而应在线上添加的最小点数。

输入

第一行包含一个整数 n (3 ≤ n ≤ 100 000) — 点数。

第二行包含整数序列 x1, x2, ..., xn (- 109 ≤ xi ≤ 109) — 点的坐标。所有这些坐标都是不同的。分数可以按任意顺序给出。

输出

打印一个整数 m — 为使所有相邻点之间的距离相等而应在线上添加的最小点数。

示例

输入 #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

注意

在第一个示例中,您可以添加一个坐标为 0 的点。

在第二个示例中,所有相邻点之间的距离已经相等,因此您不应添加任何内容。