군계일학

면접 대비

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

요약

정수 수열이 주어질 때, 원래 순서를 유지하면서 값이 공차 1인 등차수열을 이루는 가장 긴 부분수열의 길이를 구한다.

문제

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

수열 중 임의의 항 $i$ 에 대해 $a_i = a_1 + (i-1)$ 을 만족해야 한다.

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

첫째 줄에 수열의 길이 $N$ ( $1 \le N \le 100,000$ )이 주어진다. 다음 줄에 $a_i$ ( $1 \le i \le N$ , $1 \le a_i \le 1,000,000$ )가 주어진다.

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