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.
def get_len(a, b):
    if a[0]>=b[0]:
        c = a
        a = b
        b = c
    i = 0
    j = 0
    res = 2
    while i<len(a) and j<len(b):
        while a[i]<=b[j]:
            i+=1
            if i==len(a):
                break
        if i==len(a):
                break
        res+=1
        while a[i]>=b[j]:
            j+=1
            if j==len(b):
                break
        if j==len(b):
                break
        res+=1
    return res


n = int(input())
a = [int(e) for e in input().split()]
d = dict()
keys = []
for i in range(len(a)):
    x = a[i]
    if x in d:
        d[x].append(i)
    else:
        d[x] = [i]
        keys.append(x)
ans = 0
for i in range(len(keys)):
    x = keys[i]
    for j in range(i+1, len(keys)):        
        y = keys[j]
        if x==y:
            continue
        
        i1 = 0
        j1 = 0
        #print("___")
        #print(d[x], d[y])
        xi = get_len(d[x], d[y])        
        #print(xi)
        ans = max(ans, xi)
ans1 = [len(d[e]) for e in d]
ans = max(ans, max(ans1))
print(ans)
# 3 1 3 1 3
        
