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.
from sys import stdin; input=stdin.readline
volt=[0]*(10**6+8)

n=int(input())
INF=n+9
first=[INF]*INF
nxt=[0]*INF
arr=[0]*INF
frek=[0]*INF

def merge(i,j):
  i,j=first[i],first[j]
  ans=0
  while i!=INF or j!=INF:
    if(i<j):
      while i<j: i=nxt[i]
      ans+=1
    else:
      while j<i: j=nxt[j]
      ans+=1
  return ans

i=1
ndiff=0
for v in input().split():
  v=int(v)
  if volt[v]==0:
    ndiff+=1
    volt[v]=ndiff
  vv=volt[v]
  arr[i]=vv; i+=1
  frek[vv]+=1

for i in range(n,0,-1):
  v=arr[i]
  nxt[i]=first[v]
  first[v]=i

#print(nxt[:ndiff+1])
ans=max(frek[1:ndiff+1])
for i in range(1,ndiff):
  for j in range(i+1,ndiff+1):
    
    if frek[i]+frek[j]<=ans: continue
    ans=max(ans,merge(i,j))      

print(ans)
