잠자리가 겹치지 않는 소

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N마리 소의 브랜드 번호를 K로 나눈 나머지가 모두 다르게 되는 가장 작은 K를 구합니다.

난이도: 쉬움10점 중 3점
유형: 완전 탐색, 해시맵
정답자: 아직 제출이 없습니다

문제

FJ에게는 소 $N$ 마리 ( $1 \le N \le 5000$ )가 있다. 소들은 외양간의 칸 $K$ 개에서 자며, 칸 번호는 $0$ 부터 $K-1$ 까지 붙어 있다. $i$ 번째 소에게는 고유한 낙인 번호 $S_i$ ( $1 \le S_i \le 1{,}000{,}000$ )가 있다. $i$ 번째 소는 $S_i \bmod K$ 번 칸에서 잔다. 두 소가 같은 칸을 함께 쓰는 일은 없다.

소들과 낙인 번호가 주어졌을 때, 어느 두 소도 같은 칸에서 자지 않도록 하는 최소 $K$ 를 구하라.

입력

첫 줄에 정수 $N$ 이 주어진다. 이어지는 $N$ 개의 줄에는 소의 낙인 번호가 한 줄에 하나씩 주어진다.

출력

조건을 만족하는 최소 $K$ 의 값을 한 줄에 출력한다.

예제1

예제 1
입력
```
5
4
6
9
10
13
```
예상 출력
```
8
```