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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long INF = 0x3F3F3F3F3F3F3F3F;
const long long MOD = 1e9 + 7;
long double EPS = 1e-12;
short rain() {
  {
    long long n;
    cin >> n;
    vector<long long> a(n);
    for (auto &i : a) cin >> i;
    map<long long, long long> normal;
    long long x = 0;
    for (auto i : a) {
      if (normal.find(i) != normal.end()) continue;
      normal[i] = x++;
    }
    for (auto &i : a) i = normal[i];
    long long cnt[x], ans = 1;
    memset(cnt, 0, sizeof(cnt));
    for (auto i : a) cnt[i]++, ans = max(ans, cnt[i]);
    long long bw[x], ba[x], inc[x];
    for (long long i = (0); i <= (x - 1); i++) {
      memset(bw, 0, sizeof(bw)), memset(ba, 0, sizeof(ba)),
          memset(inc, 0, sizeof(inc));
      long long j = 0, enc = 0;
      while (j < n) {
        if (j == 0 || enc == cnt[i]) {
          while (j < n && a[j] != i) {
            if (enc == 0 && ba[a[j]] == 0)
              ba[a[j]]++;
            else if (enc == cnt[i] && ba[a[j]] == 1)
              ba[a[j]]++;
            j++;
          }
        } else {
          long long J = j;
          while (j < n && a[j] != i) {
            if (inc[a[j]] == 0) {
              inc[a[j]] = 1;
              bw[a[j]]++;
            }
            j++;
          }
          while (J < j) inc[a[J]] = 0, J++;
        }
        enc++, j++;
      }
      for (long long k = (0); k <= (x - 1); k++)
        ans = max(ans, bw[k] * 2 + 1 + ba[k]);
    }
    cout << ans << '\n';
  }
  return 0;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long start = 1000 * clock() / CLOCKS_PER_SEC;
  cout << fixed << setprecision(15);
  rain();
  cerr << 1000 * clock() / CLOCKS_PER_SEC - start << "ms\n";
}
