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 <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

int mp[5005][5005];
int dp[5005][5005];

int main(){

	int n;cin >> n;
	vector<ll> v(n);

	REP(i,n)cin >> v[i];
	sort(ALL(v));

	REP(i,5005)REP(j,5005){
		mp[i][j] = -1;
		dp[i][j] = 2;
	}

	REP(i,n){
		int k = i;
		for(ll j = i+1;j < n;j++){
			while(k < n && 2 * v[j] - v[i] > v[k])k++;
			if(k < n && 2 * v[j] - v[i] == v[k])mp[i][j] = k;
		}
	}

	REP(i,n){
		for(ll j = i+1;j < n;j++){
			if(mp[i][j] != -1){
				ll k = mp[i][j];
				dp[j][k] = max(dp[j][k], dp[i][j] + 1);
			}
		}
	}

	int ans = 0;
	REP(i,n){
		REP(j,n){
			ans = max(ans, dp[i][j]);
		}
	}

	cout << ans << endl;

	return 0;
}

