Gena loves sequences of numbers. Recently, he has discovered a new type of sequences which he called an almost arithmetical progression. A sequence is an almost arithmetical progression, if its elements can be represented as:

  * a1 = p, where p is some integer; 
  * ai = ai - 1 + ( - 1)i + 1·q (i > 1), where q is some integer. 



Right now Gena has a piece of paper with sequence b, consisting of n integers. Help Gena, find there the longest subsequence of integers that is an almost arithmetical progression.

Sequence s1, s2, ..., sk is a subsequence of sequence b1, b2, ..., bn, if there is such increasing sequence of indexes i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n), that bij = sj. In other words, sequence s can be obtained from b by crossing out some elements.

Input

The first line contains integer n (1 ≤ n ≤ 4000). The next line contains n integers b1, b2, ..., bn (1 ≤ bi ≤ 106).

Output

Print a single integer — the length of the required longest subsequence.

Examples

Input

2
3 5


Output

2


Input

4
10 20 10 30


Output

3

Note

In the first test the sequence actually is the suitable subsequence. 

In the second test the following subsequence fits: 10, 20, 10.
#include <bits/stdc++.h>
using namespace std;
long long int mod = 1000000007;
long long int MINF = -1000000000000000000;
long long int powmod(long long int a, long long int b) {
  long long int res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long int gcd(long long int a, long long int b) {
  return b ? gcd(b, a % b) : a;
}
const long long int MAXN = 1000005;
void magic(int n, int *ar) {
  set<int> s;
  map<int, int> m;
  for (int i = 0; i < n; i++) s.insert(ar[i]);
  int size = 0;
  for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
    m[*it] = size++;
  }
  for (int i = 0; i < n; i++) ar[i] = m[ar[i]];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t = 1;
  while (t--) {
    int n = 0, m, flag = 0, sum = 0, c = 0, flag1 = 0, ans = 0;
    cin >> n;
    int b[n];
    map<int, int> mp1;
    for (int i = (0); i < (n); i++) {
      cin >> b[i];
      mp1[b[i]]++;
    }
    magic(n, b);
    for (auto i : mp1) {
      c = max(c, i.second);
    }
    vector<int> v;
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
    ans = 1;
    ans = max(c - 1, ans);
    for (int i = (0); i < (n); i++) {
      v.push_back(b[i]);
      for (int j = (v.size() - 1 - 1); j >= (0); j--) {
        if (b[i] != v[j]) {
          if (dp[b[i]][v[j]] % 2 == 1) {
            ans = max(++dp[b[i]][v[j]], ans);
          }
          if (dp[v[j]][b[i]] % 2 == 0) {
            ans = max(++dp[v[j]][b[i]], ans);
          }
        }
      }
    }
    if (n == 1) ans = 0;
    cout << ans + 1 << endl;
  }
  return 0;
}
