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;
const int mod = 1e9 + 7;
const int N = 4004;
const int MAXE = 1e6 + 2;
vector<int> nextidx[MAXE];
int a[N];
signed main() {
  int turn, last, n, ans = 1, cur, mx = 0;
  scanf("%d", &n);
  set<int> s;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    nextidx[a[i]].push_back(i);
    s.insert(a[i]);
  }
  for (int i : s) mx = max(mx, (int)nextidx[i].size());
  ans = mx;
  if (n == 1) {
    return puts("1"), 0;
  }
  for (int i : s) {
    for (int j : s) {
      if (i == j) continue;
      cur = 2;
      auto pos =
          upper_bound(nextidx[j].begin(), nextidx[j].end(), nextidx[i][0]);
      if (pos == nextidx[j].end()) continue;
      last = *pos;
      turn = 0;
      while (true) {
        if (turn) {
          auto it = upper_bound(nextidx[j].begin(), nextidx[j].end(), last);
          if (it == nextidx[j].end())
            break;
          else {
            cur++;
            last = *it;
          }
        } else {
          auto it = upper_bound(nextidx[i].begin(), nextidx[i].end(), last);
          if (it == nextidx[i].end())
            break;
          else {
            cur++;
            last = *it;
          }
        }
        turn = !turn;
      }
      ans = max(ans, cur);
    }
  }
  printf("%d\n", ans);
  return 0;
}
