Cows in Bed

Interview

Time limit1sMemory limit1024 MB

Summary

Find the smallest K such that the N brand numbers all have distinct remainders when divided by K.

Level: Easy3 of 10
Topics: Brute force, Hash map
Solved: No attempts yet

Problem

FJ has $N$ cows ( $1 \le N \le 5000$ ) who sleep in a barn with $K$ stalls numbered $0$ to $K-1$ . The $i$ -th cow has a unique brand number $S_i$ ( $1 \le S_i \le 1{,}000{,}000$ ). Cow $i$ sleeps in stall $S_i \bmod K$ . Cows never share a stall.

Given the cows and their brands, find the minimum $K$ such that no two cows sleep in the same stall.

Input

The first line contains one integer $N$ . Each of the next $N$ lines contains one cow's brand number.

Output

Print a single line containing the minimum value of $K$ .

Examples1

Example 1
Input
```
5
4
6
9
10
13
```
Expected output
```
8
```