問題

長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます．
$A$ の（連続するとは限らない）部分列であって，等差数列になるものの長さの最大値を答えてください．

制約

• 入力はすべて整数
• $1\le N\le 800$
• $1\le A_i\le 10^9$

入力

入力は以下の形式で標準入力から与えられる．

$N$
$A_1\;A_2\;\cdots\;A_N$

出力

答えを整数で出力しなさい．

入出力例

5
1 4 5 3 2

3

部分列 $(A_2,A_4,A_5)=(4,3,2)$ は公差 $-1$ の等差数列になっています．

5
1 1 1 1 1

5

$A$ 自身が公差 $0$ の等差数列になっています．

12
3 1 4 1 5 9 2 6 5 3 5 8

4