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.
import os, sys, atexit
range = xrange
from cStringIO import StringIO as BytesIO
sys.stdout = BytesIO()
atexit.register(lambda: os.write(1, sys.stdout.getvalue()))
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
from sys import stdin
from collections import *

rints = lambda: [int(x) for x in input().split()]
n, a, ans = int(input()), rints(), 0
mem, lst = [0] * (1000001), [-1] * (1000001)

for i in range(n):
    for j in range(i, n):
        if a[j] == a[i]:
            mem[a[i]] += 1
        elif lst[a[i]] >= lst[a[j]]:
            mem[a[j]] += 2

        lst[a[j]] = j

    for j in range(i, n):
        if lst[a[i]] > lst[a[j]]:
            ans = max(ans, mem[a[j]] + 1)
        else:
            ans = max(ans, mem[a[j]])
        if a[j] != a[i]:
            mem[a[j]], lst[a[j]] = 0, -1
    mem[a[i]], lst[a[i]] = 0, -1

print(ans)
