BoB004-H: Arithmetic Subsequence

2 secs 1024 MB
kyaneko999

問題


長さ の数列 が与えられます.
の(連続するとは限らない)部分列であって,等差数列になるものの長さの最大値を答えてください.

制約


  • 入力はすべて整数

入力


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


出力


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

入出力例


入力例1
5
1 4 5 3 2
出力例1
3

部分列 は公差 の等差数列になっています.

入力例2
5
1 1 1 1 1
出力例2
5

自身が公差 の等差数列になっています.

入力例3
12
3 1 4 1 5 9 2 6 5 3 5 8
出力例3
4

提出


Go (1.14)