Acka의 리듬 세상

시간 제한2초메모리 제한512 MB

요약

서로 다른 N개의 탭 시각이 주어질 때, 어떤 정수 k >= 2와 나머지에 대해 같은 나머지를 갖는 시각의 최대 개수를 구한다.

난이도: 보통10점 중 7점
유형: 정수론, 수학, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

새 리듬 게임 Acka의 리듬 세상에서는 화면을 터치한 시각만으로 점수를 매긴다.

터치 시각을 $N$ 개 모은 뒤, $2$ 이상의 정수 $k$ 와 임의의 정수 $l$ 에 대하여 $f(k, l)$ 을 $ck + l$ 꼴로 나타낼 수 있는 터치 시각의 개수라고 정의한다. 여기서 $c$ 는 정수이다. 즉 $f(k, l)$ 은 $l$ 과 $k$ 로 나눈 나머지가 같은 터치 시각의 개수이다.

얻는 점수는 모든 가능한 $k$ 와 $l$ 에 대한 $f(k, l)$ 중 가장 큰 값이다.

터치 시각이 주어질 때 점수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 터치 횟수 $N$ 이 주어진다( $1 \le N \le 1000$ ).

둘째 줄에 터치 시각 $N$ 개가 오름차순으로 공백으로 구분되어 주어진다. 모든 시각은 서로 다르며 $0$ 이상 $2000000$ 이하의 정수이다.

출력

규칙을 적용하여 얻을 수 있는 점수를 첫째 줄에 출력한다.

힌트

정수 $l$ 을 바꾸는 것은 $k$ 로 나눈 나머지를 고르는 것과 같다. 따라서 어떤 터치 시각과 나머지가 같은 $l$ 을 고르는 것이 항상 이득이므로 $l$ 은 터치 시각 중 하나로 두어도 된다. 또한 $k$ 가 모든 터치 시각의 차이보다 크면 서로 다른 시각은 서로 다른 나머지를 가지므로 점수는 $1$ 이다.

예제3

예제 1
입력
```
3
3 6 9
```
예상 출력
```
3
```
예제 2
입력
```
5
1 2 3 6 7
```
예상 출력
```
3
```

예제 3

입력

10
1 5 10 50 100 500 1000 5000 9999 10000

예상 출력