题目描述

Z同学近期喜欢上了数字序列。然而他发现了一种新的序列。把这个序列成为z序列。

z序列可以表示为：

• 1、$\red{A_1 = P}$ , $\red P$可以是任何一个整数
• 2、$\red{A_i = A_{i-1} + (-1) ^{i+1} * Q}$ ($\red {i > 1}$) ,$\red Q$可以是任何整数

现在Z同学有个序列，长度为$\red N$ 。

整个序列由$\red N$个整数组成。现在请你帮Z同学找出最长的Z序列。

序列$\red {S_1 ,S_2 ,S_3 ......S_k}$是序列$\red {B_1 ,B_2 ,B_3 .....B_n}$的子序列。

如果下标是$\red {i_1 ,i_2 ,i_3 ......i_k (1 <= i_1 < i_2 < .... < i_k <= i_n )}$。 那么$\red {B_{ij} = S_j}$

换句话说，你可以在B序列当中删除一些元素可以得到序列$\red S$。

输入格式

第一行输入一个$\red N$($\red {N <= 4000}$)

接下来的$\red 1$行总共有$\red N$个数字，代表序列的元素。

分别是$\red {B_1 ,B_2 ,B_3 .....B_n}$。

输出格式

输出一个整数，代表B序列当中的最长的Z序列的长度。

样例

样例输入1

2
3 5

样例输出1

2

样例输入2

4
10 20 10 30

样例输出2

3

提示

样例1：

样例$\red 1$ 本身就是一个Z序列，所以长度是$\red 2$

样例2:

$\red {10,20,10}$ 符合Z序列，所以最长为$\red 3$