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;
using ll = long long;
using ld = long double;
namespace io {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(ld& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = {a, b};
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.f, p.s);
}
template <class T>
void re(vector<T>& a) {
  for (int i = (0) - (1 - 2 * (0 > ((int)a.size())) < 0);
       (1 - 2 * (0 > ((int)a.size()))) > 0 ? i < (((int)a.size()))
                                           : i >= (((int)a.size()));
       i += (1 - 2 * (0 > ((int)a.size()))))
    re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = (0) - (1 - 2 * (0 > SZ) < 0);
       (1 - 2 * (0 > SZ)) > 0 ? i < (SZ) : i >= (SZ); i += (1 - 2 * (0 > SZ)))
    re(a[i]);
}
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(ll x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(ld x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template <class T>
void pr(const complex<T>& x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.f, ", ", x.s, "}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
void pc() { pr("]\n"); }
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
}  // namespace io
using namespace io;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
ll n;
unordered_map<ll, vector<int>> mp;
int find(int u, int v) {
  if (u == v) return mp[v].size();
  int n = ((int)mp[u].size()), m = ((int)mp[v].size());
  int i = 0, j = 0, ans = 1, last;
  bool cur = 0;
  if (mp[u][i] < mp[v][j]) {
    cur = 0;
    last = mp[u][i];
    i++;
  } else {
    cur = 1;
    last = mp[v][j], j++;
  }
  while (i < n or j < m) {
    if (i == n) {
      if (cur == 0 and last < mp[v].back())
        return ans + 1;
      else
        return ans;
    } else if (j == m) {
      if (cur == 1 and last < mp[u].back()) {
        return ans + 1;
      } else
        return ans;
    } else if (cur == 0) {
      while (j < m and mp[v][j] < last) j++;
      if (j < m) last = mp[v][j], ans++, j++, cur = 1;
    } else {
      while (i < n and mp[u][i] < last) i++;
      if (i < n) last = mp[u][i], ans++, i++, cur = 0;
    }
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  re(n);
  int a[n];
  unordered_set<ll> st;
  for (int i = (0) - (1 - 2 * (0 > n) < 0);
       (1 - 2 * (0 > n)) > 0 ? i < (n) : i >= (n); i += (1 - 2 * (0 > n)))
    re(a[i]), mp[a[i]].push_back(i), st.insert(a[i]);
  int ans = 0;
  vector<int> ss;
  for (auto i : st) ss.push_back(i);
  for (int ii = (0) - (1 - 2 * (0 > ((int)ss.size())) < 0);
       (1 - 2 * (0 > ((int)ss.size()))) > 0 ? ii < (((int)ss.size()))
                                            : ii >= (((int)ss.size()));
       ii += (1 - 2 * (0 > ((int)ss.size())))) {
    for (int jj = (ii) - (1 - 2 * (ii > ((int)ss.size())) < 0);
         (1 - 2 * (ii > ((int)ss.size()))) > 0 ? jj < (((int)ss.size()))
                                               : jj >= (((int)ss.size()));
         jj += (1 - 2 * (ii > ((int)ss.size())))) {
      int i = ss[ii], j = ss[jj];
      ckmax(ans, find(i, j));
    }
  }
  ps(ans);
}
