今天蒜头君拿到了一个数轴，上边有 nn 个点，但是蒜头君嫌这根数轴不够优美，想要通过加一些点让它变优美，所谓优美是指考虑相邻两个点的距离，最多只有一对点的距离与其它的不同。
蒜头君想知道，他最少需要加多少个点使这个数轴变优美。
输入格式
输入第一行为一个整数 n(1 \leq n \leq 10^5)n(1≤n≤105)，表示数轴上的点数。
第二行为 nn 个不重复的整数 x_1,x_2,...,x_n(-10^9 \leq x_i \leq 10^9)x1?,x2?,...,xn?(?109≤xi?≤109)，表示这些点的坐标，点坐标乱序排列。
输出格式
输出一行，为一个整数，表示蒜头君最少需要加多少个点使这个数轴变优美。
样例输入
4 1 3 7 15
样例输出
1
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int dis[maxn];
int gcd1[maxn];
int gcd2[maxn];
long long sum;
int Gcd(int a,int b)
{return b==0?a:Gcd(b,a%b);
}
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}if(n<=3){cout<<0<<endl;return 0;}sort(a,a+n);sum=0;for(int i=1;i<n;i++){dis[i]=a[i]-a[i-1];sum+=dis[i];}int d=dis[0];for(int i=1;i<=n-1;i++){d=Gcd(d,dis[i]);gcd1[i]=d;}d = dis[n];for(int i = n-1; i >= 1; i--){d = Gcd(d,dis[i]);gcd2[n-i] = d;}int Min= 0x3f3f3f3f;int temp;for(int i=1;i<n;i++){if(i==1)temp=(sum-dis[i])/gcd2[n-2];else if(i==n-1)temp=(sum-dis[i])/gcd1[n-2];elsetemp=(sum-dis[i])/Gcd(gcd1[i-1],gcd2[n-i-1]);Min=min(Min,temp-n+2);}cout<<Min;}