4378. [郑轻校赛 2026] 等差数列

Problem C. 等差数列

给定 $n$ 个互不相同的整数，请你找出最大的正整数 $d$，使得存在一个公差为 $d$ 的等差数列（其所有项均为整数），并且这 $n$ 个数都是该等差数列中的项。

Input

第一行包含一个整数 $n$ $(2 \le n \le 10^6)$。

第二行包含 $n$ 个互不相同的整数 $A_1, A_2, \dots, A_n$ $( -10^6 \le A_i \le 10^6 )$。

Output

输出一个整数，表示最大的可能公差。

Example

样例输入1

3
5 1 3

样例输出1

2

样例输入2

4
9 0 3 15

样例输出2

3

Note

样例1：公差为 $2$ 的等差数列 $\{\dots,-1,1,3,5,7,\dots\}$ 包含给定所有数。

样例2：公差为 $3$ 的等差数列 $\{\dots,-3,0,3,6,9,12,15,\dots\}$ 包含给定所有数。

来源