Description

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 ≠ vj if i ≠ 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,dp[i][j]表示i和j作为前两项时的数列长度，如果先枚举第一项(O(N)),然后第二项如果和第三项在第一项的同一侧的话就是(O(N^2))，整体复杂度是(O(N^3))，难以接受，而如果先枚举第二项，然后第一项和第三项在第二项两侧，根据a[j]+a[k]=2*a[i]可以将复杂度降为O(N^2)

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int a[],dp[][];

 int main(){

     int n;

     scanf("%d",&n);

     for(int i=;i<=n;i++)scanf("%d",&a[i]);

     for(int i=;i<=n;i++){

         for(int j=i;j<=n;j++){

             if(i!=j)dp[i][j]=;

             else dp[i][j]=;

         }

     }

     sort(a+,a++n);

     int ans=;

     for(int i=n-;i>=;i--){

         int j=i-;

         int k=i+;

         while(j>=&&k<=n){

             if(a[j]+a[k]==*a[i]){dp[j][i]=dp[i][k]+;ans=max(ans,dp[j][i]);k++;j--;}

             else if(a[j]+a[k]<*a[i]){k++;}

             else {j--;}

         }

     }

     cout<<ans<<endl;

     return ;

 }