Cows in Bed

면접 대비

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

요약

N개의 브랜드 번호가 주어질 때, 각 번호를 K로 나눈 나머지가 모두 서로 다르도록 하는 최소 K를 구합니다.

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

문제

FJ는 $0$ 부터 $K-1$ 까지 번호가 매겨진 외양간 $K$ 개가 있는 헛간에서 잠을 자는 소 $N$ 마리( $1 \le N \le 5000$ )를 키운다. 각 소에게는 고유한 브랜드인 정수 $S_i$ ( $1 \le S_i \le 1{,}000{,}000$ )가 있다. 소는 외양간 번호 $S_i \bmod K$ 에서 잔다. 소들은 잠자리로 같은 외양간을 함께 쓰려 하지 않는다.

소들과 브랜드가 주어질 때, 어떤 두 소도 같은 외양간에서 자지 않도록 하는 최소의 $K$ 를 구하라.

입력

첫 줄에 정수 $N$ 이 주어진다. 다음 $N$ 개의 줄에는 각각 소의 브랜드를 나타내는 정수 하나가 주어진다.

출력

어떤 두 소도 같은 외양간에서 자지 않는 최소의 $K$ 값을 한 줄에 출력한다. 모든 유효한 입력은 제한 시간 안에 풀 수 있다.

예제1

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