시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 112 30 16 19.048%

문제

shake!에서 새로운 게임인 'Acka의 리듬 세상'이라는 게임을 발표했다.

이 게임의 목적은 스마트폰 화면을 리듬감있게 터치하는 것이라서, 박자에 관계 없이 화면을 규칙적으로 클릭하면 높은 점수를 얻을 수 있다. (하지만, 게임의 재미를 위해서 이러한 사실을 유저에게 알려주지는 않는다.)

게임 한 판이 끝나고 나면, 유저가 얼마나 리듬감있게 화면을 터치했는지에 대한 점수를 제공해준다.

2 이상의 자연수 k와 정수 l에 대해서 f(k, l)을 다음과 같이 정의하자:

f(k, l) = (N개의 화면을 터치한 시간 중 ck + l 꼴(단, c는 정수)로 나타낼 수 있는 수의 개수)

이때 유저가 얻을 수 있는 점수는 가능한 f(k, l)들 중에서 최댓값으로 정해진다.

화면을 터치한 시간들이 주어질 때, 위의 점수 측정 방식을 적용하여 얻을 수 있는 점수를 구하는 프로그램을 작성하여라.

입력

게임 도중에 스마트폰 화면을 터치한 횟수 N(1 ≤ N ≤ 1,000)이 주어진다.

다음 줄에 화면을 터치한 시간이 오름차순으로 N개가 주어진다. N개의 수는 모두 다르며, 0 이상 2,000,000 이하의 정수이다.

출력

화면을 터치한 시간의 정보를 바탕으로 'Acka의 리듬 세상'의 규칙을 적용했을 때 얻을 수 있는 점수를 출력한다.

예제 입력 1

3
3 6 9

예제 출력 1

3

예제 입력 2

5
1 2 3 6 7

예제 출력 2

3

예제 입력 3

10
1 5 10 50 100 500 1000 5000 9999 10000

예제 출력 3

8

힌트

예제 1: f(3, 0) = 3이 최댓값이다.

예제 2: f(2, 1) = 3이 최댓값이다.

예제 3: f(5, 0) = 8이 최댓값이다.