Cows in Bed

FJ has N (1 ≤ N ≤ 5000) cows who sleep in stalls in a barn with K stalls numbered 0..K-1. The i-th cow has a unique brand that is a number Si (1 ≤ Si ≤ 1,000,000). Each cow knows where to sleep because she sleeps in stall number Si mod K. Of course, cows will never want to share a stall for sleeping.

Given a set of cows and their brands, determine the minimum K such that no two cows sleep in the same stall.

• Line 1: One integer: N
• Lines 2..N+1: One integer that is a cows brand

A single line with the minimum value of K on it. All legal input datasets can be solved within the allotted time.