An arithmetic progression is a sequence of numbers a1, a2, . . . , ak where the difference of consecutive members ai+1 −ai is a constant (1 ≤ i ≤ k −1). For example, the sequence 5, 8, 11, 14, 17 is an arithmetic progression of length 5 with the common difference 3. In this problem, you are requested to find the longest arithmetic progression which can be formed selecting some numbers from a given set of numbers. For example, if the given set of numbers is {0, 1, 3, 5, 6, 9}, you can form arithmetic progressions such as 0, 3, 6, 9 with the common difference 3, or 9, 5, 1 with the common difference −4. In this case, the progressions 0, 3, 6, 9 and 9, 6, 3, 0 are the longest.

Input

The input consists of a single test case of the following format. n v1 v2 · · · vn n is the number of elements of the set, which is an integer satisfying 2 ≤ n ≤ 5000. Each vi (1 ≤ i ≤ n) is an element of the set, which is an integer satisfying 0 ≤ vi ≤ 109 . vi ’s are all different, i.e., vi 6= vj if i 6= j.

Output

Output the length of the longest arithmetic progressions which can be formed selecting some numbers from the given set of numbers.

Sample Input

6

0 1 3 5 6 9

Sample Output

4

思路：题意就是让你求最长等差序列的长度，dp[i][j] 表示区间[i, j] 的最大等差序列长度，从当前位置往前往后找满足条件的区间，如果有就加一，边界dp[i][i + 1] = 2，不难理解，其实任意dp[i][j]（j！=i） 最小都为2.

#include<set>
#include<map>
#include<stack>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 5e3 + 10;
const int inf = 0x3f3f3f3f;
int dp[maxn][maxn];
int a[maxn];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    int ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        int l = i - 1;
        for(int j = i + 1; j <= n; ++j)
        {
            dp[i][j] = 2;
            while(l >= 1 && a[j] - a[i] > a[i] - a[l])
                l--;
            if(l >= 1 && a[j] - a[i] == a[i] - a[l])
                dp[i][j] = dp[l][i] + 1;
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}