等差数列是指一个数列 $a_1, a_2, \dots, a_k$，其中相邻项之差 $a_{i+1} - a_i$ 为常数（$1 \le i \le k-1$）。例如，数列 $5, 8, 11, 14, 17$ 是一个长度为 $5$、公差为 $3$ 的等差数列。

在本题中，你需要从给定的数字集合中选出一些数字，找出能构成的最长等差数列。例如，如果给定的数字集合是 $\{0, 1, 3, 5, 6, 9\}$，你可以构成公差为 $3$ 的等差数列 $0, 3, 6, 9$，或者公差为 $-4$ 的等差数列 $9, 5, 1$。在这种情况下，数列 $0, 3, 6, 9$ 和 $9, 6, 3, 0$ 是最长的。

输入格式

输入包含单个测试用例，格式如下：

$n$ $v_1 \ v_2 \ \dots \ v_n$

$n$ 是集合中元素的个数，为一个满足 $2 \le n \le 5000$ 的整数。每个 $v_i$ ($1 \le i \le n$) 是集合中的元素，为一个满足 $0 \le v_i \le 10^9$ 的整数。所有 $v_i$ 互不相同，即当 $i \neq j$ 时，$v_i \neq v_j$。

输出格式

输出从给定数字集合中选出一些数字所能构成的最长等差数列的长度。

样例

样例输入 1

6
0 1 3 5 6 9

样例输出 1

4

样例输入 2

7
1 4 7 3 2 6 5

样例输出 2

7

样例输入 3

5
1 2 4 8 16

样例输出 3

2