Same Remainder

Interview

Time limit2sMemory limit128 MB

Summary

Given a sequence, find the largest divisor D so that all numbers leave the same remainder when divided by D.

Level: Medium4 of 10
Topics: Number theory, Math, Array
Solved: No attempts yet

Problem

For integers N and D, let Q be the quotient and R be the remainder when N is divided by D. Then R = N - Q × D.

You are given a sequence of n integers. There may be an integer D such that every number in the sequence leaves the same remainder when divided by D. Depending on the sequence, several such values of D may exist.

Find the largest possible D for the given sequence.

Input

The first line contains n (1 ≤ n ≤ 1,000). The second line contains n integers whose absolute values do not exceed 1,000,000.

Output

Print the largest possible D on the first line. The input is guaranteed to be a case where such a largest value exists.

Examples3

Example 1
Input
```
4
701 1059 1417 2312
```
Expected output
```
179
```
Example 2
Input
```
5
14 23 17 32 122
```
Expected output
```
3
```
Example 3
Input
```
5
14 -22 17 -31 -124
```
Expected output
```
3
```