Arithmetic Progressions

An arithmetic progression is a sequence of numbers $a_1, a_2, ..., a_k$ where the difference of consecutive members $a_{i+1} - a_i$ is a constant ($1 \leq i \leq 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$
$v_1$ $v_2$ ... $v_n$


$n$ is the number of elements of the set, which is an integer satisfying $2 \leq n \leq 5000$. Each $v_i$ ($1 \leq i \leq n$) is an element of the set, which is an integer satisfying $0 \leq v_i \leq 10^9$. $v_i$'s are all different, i.e., $v_i \ne v_j$ if $i \ne 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 1


6
0 1 3 5 6 9


Sample Output 1


4


Sample Input 2


7
1 4 7 3 2 6 5


Sample Output 2


7


Sample Input 3


5
1 2 4 8 16


Sample Output 3


2






Example

Input

6
0 1 3 5 6 9


Output

4
#include<iostream>
#include<iomanip>
#include<stdlib.h>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<limits>
#include<numeric>
#include<unordered_map>
#include<functional>
#include<bitset>
using namespace std;

#define rep(i,s,n) for(int i=s;i<n;i++)
#define dow(i,n,s) for(int i=n-1;i>=s;i--)
#define all(a) a.begin(),a.end()
#define Sort(a) sort(a.begin(),a.end())
#define rng(a,b,e) a.begin()+b,a.begin()+e
//#define DEBUG
typedef pair<int,int> II;
typedef unsigned long ul;
typedef long long ll;
typedef unsigned long long ull;
bool compare_by_second(II a,II b) {
  if(a.second != b.second) return a.second < b.second;
  else return a.first < b.first;
}
int compare_int(const void *a,const void *b){ return *(int *)a - *(int *)b; }

const int INF = 1e+9;
const int MAX_N = 5e+3;
const int MAX_V = 1e+9;

int n;
int a_i;
int d;
int sum,mx;
unordered_map<int, int> um;
//vector<int> v;

int main() {

  cin>>n;
  int v[n];
  //v.resize(n);
  mx = 2;
  rep(i,0,n) { cin>>v[i]; um[v[i]] = 1; }
  qsort(v,n,sizeof(*v),compare_int);
#ifdef DEBUG
  rep(i,0,n) cout<<v[i]<<" , ";
  cout<<endl;
#endif
  //Sort(v);
  rep(i,0,n-2) {
    rep(j,i+1,n-1) {
      d = v[j] - v[i];
      a_i = v[j] + d;
      sum = 2;
#ifdef DEBUG
      rep(k,j+1,n) {
        if(v[k] == a_i) { a_i += d; sum++; }
        if(v[k] > a_i) break;
      }
#endif
      rep(k,0,MAX_N-2) {
        if(um.find(a_i+d*k) == um.end() || k>=MAX_N-2) break;
        //cout<<k<<boolalpha<<num[k-1]<<" , ";
        sum++;
      }
      //cout<<endl;
      //mx = max(mx,sum);
      if(sum > mx) mx = sum;
      if(mx >= n-j-1) break;
    }
    if(mx >= n-i-1) break;
  }

  cout<<mx<<endl;
  return 0;
}

