题目描述

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入描述

输入的第一行包含一个整数 N。

第二行包含 N 个整数 A1​,A2​,⋅⋅⋅,AN​。(注意 A1​ ∼ AN​ 并不一定是按等差数列中的顺序给出)

其中，2≤N≤10^5，0≤Ai​≤10^9。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

5
2 6 4 10 20

输出

10

样例说明： 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。

等差数列项数公式： 

例：1、3、5、7、9
首项：1   末项：9    公差：2     项数：5个
等差数列求和：（首项+末项）*项数/2
求项数：           （末项-首项）/公差+1
求首项：              末项-公差*（项数-1）
求末项：              首项+公差*（项数-1）
求公差：            （末项-首项）/（项数-1）

参考代码：

import os
import sys
n=int(input())
s=[int(i) for i in input().split(' ')]
s.sort()
d=s[1]-s[0]               # d 为公差
for i in range(1,n):
  if s[i]-s[i-1]<d:       
    d=s[i]-s[i-1]         #将公差更新
if d!=0:
  print(((max(s)-min(s))//d)+1)   #求项数：（末项-首项）/公差+1
else:           #当输入的这几项整数都相等时，最短的等差数列为整数个数
  print(n)