P8682 [Lanqiao Cup 2019 NOI Qualifier B] Arithmetic Progression

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?

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 one integer, the answer.

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