시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 362 74 52 19.697%

문제

N(1≤N≤2,000)개의 음 아닌 정수들이 있다. 이들 중 몇 개의 정수를 선택하여 나열하면 등차수열을 만들 수 있다. 예를 들어 4, 3, 1, 5, 7이 있을 때 1, 3, 5, 7을 선택하여 나열하면 등차수열이 된다. 이와 같이 했을 때, 등차수열의 길이가 최대 얼마까지 가능한지 알아내시오.

등차수열은 일정한 값만큼 증가하는 수열을 말한다. 이 일정한 값은 음수나 0도 될 수 있다.

입력

첫째 줄에는 숫자의 개수 N(1≤N≤2,000)이 주어지고, 다음 N개의 줄에는 정수들이 주어진다. 정수들은 1,000,000,000보다 작다.

출력

첫째 줄에 가장 긴 등차수열의 길이를 출력한다.

예제 입력

5
1
4
3
5
7

예제 출력

4

힌트