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() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int TESTS = 1;
  while (TESTS--) {
    int pres[1000005] = {0}, a, n, i, j, ans = 1, count = 0;
    cin >> n;
    vector<vector<int>> p(1000005);
    vector<int> arr;
    for (long long int i = 0; i < n; i++) {
      cin >> a;
      p[a].push_back(i);
      if (!pres[a]) {
        arr.push_back(a);
        pres[a] = 1;
      }
    }
    for (i = 0; i < arr.size(); i++) {
      ans = max(ans, (int)p[arr[i]].size());
      for (j = 0; j < arr.size(); j++) {
        if (i == j) continue;
        auto it1 = p[arr[i]].begin(), it2 = p[arr[j]].begin();
        while (true) {
          if (count & 1) {
            while (it1 != p[arr[i]].end() && *it1 <= *it2) it1++;
          } else {
            while (it2 != p[arr[j]].end() && *it2 <= *it1) it2++;
          }
          count++;
          if (it1 == p[arr[i]].end() || it2 == p[arr[j]].end()) break;
        }
        ans = max(ans, count);
        count = 0;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}
