25289번 - 가장 긴 등차 부분 수열

문제

길이가 $N$인 수열 $A$가 주어진다. $A$의 부분 수열 중, 등차 수열인 가장 긴 부분 수열의 길이를 출력하는 프로그램을 작성하자.

부분 수열과 등차 수열이 무엇인지 잘 모르는 친구들은 친절한 준서가 준비한 아래 정의를 읽어보도록 하자.

• 부분 수열이란 주어진 수열에서 1개 이상의 원소를 골라 원래 순서대로 나열하여 얻은 수열을 말한다.
• 등차 수열이란 연속한 두 항의 차이가 모두 일정한 수열을 말한다.
• 예를 들어 $\lbrace1, 3, 5, 7\rbrace$은 연속한 두 항의 차이가 3ドル-1=5-3=7-5=2$로 일정하므로 등차 수열이다.

입력

첫째 줄에 수열의 길이 $N$이 주어진다. (1ドル \leq N \leq 100,000円$)

둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. (1ドル \leq A_i \leq 100$)

출력

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

제한

힌트