该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

市政府在一条笔直的马路上种植了一些树。目前，马路上已经有 $N$ 棵树，第 $i$ 棵树的位置坐标是 $X_i$。为了让街道看起来更整齐，市长决定补种一些树，使得：

所有树（包括原有的和新种的）之间的间距必须相等。

不能移动或砍伐现有的任何一棵树，只能在空位上补种。

请问：为了满足上述要求，最少需要补种多少棵树？

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $X_1, X_2, \dots, X_N$，表示现有树的坐标。

注意：输入的坐标可能是乱序的。

输出格式

输出一个整数，表示最少需要补种的树的数量。

3
3 9 1

2

已有 $3$ 棵树，需要补种 $2$ 棵（在坐标 $5$ 和 $7$ 处）

3
1 5 9

0

三棵树已经等间距（间距为 $4$），不需要补种。

数据规模与约定

对于 $100\%$ 的数据，$1 \le N \le 2 \times 10^5$， $1 \le X_i \le 10^9$。