Problem Description

The math teacher gave Xiao Ming a problem about summing an arithmetic progression. However, the careless Xiao Ming forgot part of the sequence and only remembers $N$ integers.

Now these $N$ integers are given. Xiao Ming wants to know: how many terms does the shortest arithmetic progression that contains all these $N$ integers have?

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$ (note that $A_1 \sim A_N$ are not necessarily given in the order they appear in the arithmetic progression).

Output Format

Output one integer, the answer.

5
2 6 4 10 20

10

Hint

The shortest arithmetic progression that contains 2,6,4,10,20 is 2,4,6,8,10,12,14,16,18,20.

For all test cases, $2 \le N \le 10^5$, $0 \le A_i \le 10^9$.

Lanqiao Cup 2019 Provincial Contest B Group, Problem H.

Translated by ChatGPT 5