시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 256 MB287059246829.490%

문제

효빈이는 어떤 수열에서 군계일학 수열을 뽑아내고자 한다. 단, 뽑은 항의 순서는 기존 수열에서의 순서를 유지해야 한다. 군계일학 수열은 각 항이 서로 연속적인 수열을 의미한다. 정확한 정의는 다음과 같다.

수열 중에 어떤 임의의 항 i에 대해서, ai=a1+(i-1)을 만족해야한다.

길이가 N이고 정수로 이루어진 수열이 주어진다. 효빈이는 가장 긴 군계일학 수열을 가져가서 김승호 선생님께 자랑하려고 한다. 효빈이가 뽑아낼 수 있는 가장 긴 군계일학 수열의 크기를 출력하라.

입력

첫째 줄에 수열의 길이 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에, ai (1 ≤ i ≤ N, 1 ≤ ai ≤ 1,000,000)이 주어진다.

출력

수열에서 뽑아낼 수 있는 가장 긴 군계일학 수열의 길이를 출력한다.

서브태스크 1 (20점)

  • N ≤ 10

서브태스크 2 (15점)

  • N ≤ 1,000

서브태스크 3 (65점)

  • 문제에서 주어진 제약 조건 외 조건 없음

예제 입력 1

6
1 2 3 4 5 6

예제 출력 1

6

예제 입력 2

3
1 5 2

예제 출력 2

2

출처

High School > 부산일과학고 > BSIS배 Code Festival E번

채점 및 기타 정보

  • 예제는 채점하지 않는다.