P1154 Cow Stall Assignment

Farmer John has $N(1 \le N \le 5000)$ cows. Each cow has a unique ID $s_i$, different from every other cow. All the cows sleep in a barn that has $K$ stalls, labeled $0$ to $K-1$. No two cows may share the same stall. Each cow knows which stall to sleep in because John taught them division: the stall index for the $i$-th cow is $S_i \bmod K$. Find the smallest $K$ such that the assignment is valid (i.e., all cows are assigned to distinct stalls).

The first line contains a positive integer $N$. Lines $2$ through $N+1$ each contain one integer, the ID of a cow.

Output a single integer, the minimal $K$. For all testdata, such a $K$ is guaranteed to exist.

$S_i(1\le S_i \le 1000000)$ Translated by ChatGPT 5