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>
std::vector<long long> vec;
const long long MAX_N = 4001;
short memo[MAX_N][MAX_N];
std::unordered_map<long long, std::set<long long>> idx;
static short go(const long long& prev, const long long& curr) {
  if (memo[prev][curr] != -1) return memo[prev][curr];
  auto it = idx[vec[prev]].upper_bound(curr);
  return memo[prev][curr] = it == idx[vec[prev]].end() ? 0 : 1 + go(curr, *it);
}
int main(void) {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  for (long long i = 0; i < MAX_N; ++i) std::fill(memo[i], memo[i] + MAX_N, -1);
  long long n;
  std::cin >> n;
  vec.resize(n);
  for (long long i = 0; i < n; ++i) {
    std::cin >> vec[i];
    idx[vec[i]].insert(i);
  }
  short best = 1;
  for (long long i = 0; i < n; ++i) {
    std::unordered_set<long long> did_second;
    for (long long j = i + 1; j < n; ++j) {
      if (did_second.count(vec[j])) continue;
      did_second.insert(vec[j]);
      short res = 2 + go(i, j);
      best = std::max(best, res);
    }
  }
  std::cout << best << "\n";
  return 0;
}
