A. 几乎等差数列

每个测试的时间限制：$5$ 秒
内存限制：$256$ 兆字节

Gena 喜欢数字序列。最近，他发现了一种新的序列类型，称之为几乎等差数列。一个序列被称为几乎等差数列，如果它的元素可以表示为：

• $a_1 = p$，其中 $p$ 是某个整数；
• $a_i = a_{i-1} + (-1)^{i+1} \cdot q$（$i > 1$），其中 $q$ 是某个整数。

现在 Gena 有一张纸，上面有一个由 $n$ 个整数组成的序列 $b$。请帮助 Gena 在其中找出最长的子序列，该子序列是一个几乎等差数列。

序列 $s_1, s_2, \dots, s_k$ 是序列 $b_1, b_2, \dots, b_n$ 的子序列，如果存在一个递增的下标序列 $i_1, i_2, \dots, i_k$（$1 \le i_1 < i_2 < \dots < i_k \le n$），使得 $b_{i_j} = s_j$。换句话说，序列 $s$ 可以通过删除 $b$ 中的一些元素得到。

输入
第一行包含一个整数 $n$（$1 \le n \le 4000$）。
第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 10^6$）。

输出
输出一个整数 —— 所需的最长子序列的长度。

示例

输入

2
3 5

输出

2

输入

4
10 20 10 30

输出

3

说明

• 在第一个测试中，序列本身就是一个合适的子序列。
• 在第二个测试中，以下子序列符合要求：$10, 20, 10$。