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;
int main(void) {
  int i, n, j, v[4000], ans, x, ub, l[4000], q[4000], mn = 0, mi;
  bool used[4000];
  map<int, int> M, Q, D;
  set<int> S;
  multiset<int> MS;
  set<int>::iterator sit;
  multiset<int>::iterator msit;
  memset(used, 0, sizeof used);
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &v[i]);
    S.insert(v[i]);
  }
  for (i = 0, sit = S.begin(); sit != S.end(); sit++, i++) M[*sit] = i;
  ans = 1;
  v[0] = M[v[0]];
  D[v[0]]++;
  Q[v[0]]++;
  for (i = 1; i < n; i++) {
    v[i] = M[v[i]];
    if (v[i - 1] != v[i]) D[v[i]]++;
    Q[v[i]]++;
    if ((x = Q[v[i]]) > ans) ans = x;
  }
  if (S.size() == 1) {
    printf("%d\n", Q[0]);
    return 0;
  }
  for (i = 0; i < S.size(); i++) MS.insert(-D[i]);
  ub = -*(msit = MS.begin()) - *(++msit);
  for (i = 0; i < n; i++) {
    if (!used[v[i]]) {
      mn = 0;
      memset(q, 0, sizeof q);
      memset(l, -1, sizeof l);
      used[v[i]] = true;
      l[v[i]] = i;
      for (j = i + 1; j < n; j++) {
        if (v[j] == v[i])
          l[v[i]] = j;
        else {
          if (l[v[j]] < l[v[i]]) q[v[j]]++;
          l[v[j]] = j;
          if (mn < q[v[j]]) {
            mn = q[v[j]];
            mi = j;
          }
        }
      }
      mn *= 2;
      if (l[v[i]] > mi) mn++;
    }
    if (ans < mn) ans = mn;
    if (ans >= ub) break;
  }
  printf("%d\n", ans);
  return 0;
}
