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>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const long long N = 1e5 + 1, M = 2e6 + 1;
long long n, k;
long long a[N], ans = 1;
vector<long long> poss[M];
vector<long long> nums;
bool arr[M];
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i], poss[a[i]].push_back(i);
    if (arr[a[i]]) continue;
    arr[a[i]] = 1, nums.push_back(a[i]);
  }
  for (int i = 0; i < nums.size(); i++) {
    ans = max((long long)poss[nums[i]].size(), ans);
    for (int j = i + 1; j < nums.size(); j++) {
      long long l = 0, k = 0, sub = 2;
      long long x = nums[i], y = nums[j];
      long long sn = poss[x].size(), sm = poss[y].size();
      for (int ki = 0; l < sn && k < sm; ki++) {
        if (ki % 2) {
          while (k < sm && poss[x][l] > poss[y][k]) k++;
          if (k == sm || poss[x][l] > poss[y][k]) break;
        } else {
          while (l < sn && poss[x][l] < poss[y][k]) l++;
          if (l == sn || poss[x][l] < poss[y][k]) break;
        }
        sub++;
      }
      ans = max(ans, sub);
    }
  }
  cout << ans;
}
