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.
#!/usr/bin/env python3
import io
import os
import sys

input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def printd(*args, **kwargs):
    # print(*args, **kwargs, file=sys.stderr)
    print(*args, **kwargs)
    pass


def get_str():
    return input().decode().strip()


def rint():
    return map(int, input().split())


def oint():
    return int(input())

n = oint()
b = list(rint())
index_dict = dict()

for i in range(n):
    if b[i] in index_dict:
        index_dict[b[i]].append(i)
    else:
        index_dict[b[i]] = [i]
index = []
for i in index_dict:
    index.append(index_dict[i])
max_cnt = 0

for i in range(len(index)):
    il = index[i]
    for j in range(len(index)):
        jl = index[j]
        if i == j:
            max_cnt = max(max_cnt, len(index[i]))
            continue
        ci, cj, cnt = 0, 0, 1
        ij = 'i'
        while ci != len(il) and cj != len(jl):
            if ij == 'i':
                if jl[cj] > il[ci]:
                    cnt += 1
                    ij = 'j'
                else:
                    cj += 1
            else:
                if jl[cj] < il[ci]:
                    cnt += 1
                    ij = 'i'
                else:
                    ci += 1
        max_cnt = max(max_cnt, cnt)
print(max_cnt)