题目描述

等差数列是一列数字 $a_1$, $a_2$, $\ldots$, $a_k$，其中连续项之间的差 $a_{i+1} - a_i$ 是一个常数（$1 \leq i \leq 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$ 是最长的。

输入格式

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

$$\begin{aligned} &n \\ &v_1 & v_2 & \cdots & v_n\\ \end{aligned}$$

$n$ 是集合中元素的数量，是一个满足 $2 \leq n \leq 5000$ 的整数。每个 $v_i$ （$1 \leq i \leq n$）是集合中的一个元素，是一个满足 $0 \leq v_i \leq 10^9$ 的整数。所有的 $v_i$ 互不相同，即如果 $i \neq j$，则 $v_i \neq v_j$。

输出格式

输出从给定数字集合中选出一些数字可以形成的最长等差数列的长度。

6
0 1 3 5 6 9

4

7
1 4 7 3 2 6 5

7

5
1 2 4 8 16

2