Shortest Arithmetic Sequence

Given a set of N integers that are known to be part of an arithmetic sequence, find the number of terms in the shortest arithmetic sequence that contains all these integers.

Let the given integers be \(a_1, a_2, \ldots, a_N\). Denote \(A = \min\{a_i\}\) and \(B = \max\{a_i\}\). For an arithmetic sequence starting at \(A\) with a common difference \(d\), the sequence is

[ A,; A+d,; A+2d,; \ldots,; B ]

For the sequence to contain every \(a_i\), it is necessary that \(a_i-A\) is divisible by \(d\) for all \(i\). Equivalently, \(d\) must be a positive divisor of every \(a_i - A\). In order to minimize the number of terms, you should choose the largest possible \(d\); in fact, \(d\) should equal the greatest common divisor (\(\gcd\)) of \(\{a_i - A \mid 1 \le i \le N\}\). Then the number of terms in the sequence is given by

[ \text{terms} = \frac{B - A}{d} + 1. ]

Note: If \(N=1\), then the sequence consists of just that one term.

inputFormat

The first line contains an integer N (\(1 \le N \le 10^5\)) denoting the number of given integers. The second line contains N space-separated integers \(a_1, a_2, \ldots, a_N\).

outputFormat

Output a single integer representing the number of terms in the shortest arithmetic sequence that contains all the given integers.

sample

4
5 15 10 20

4