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,io
from sys import stdout
import collections
# import random
# import math
# from operator import itemgetter
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from collections import Counter
# from decimal import Decimal
# import heapq
# from functools import lru_cache

# import sys
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(102400000)

# from functools import lru_cache
# @lru_cache(maxsize=None)

######################
# --- Maths Fns  --- #
######################
def primes(n):
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

def binomial_coefficient(n, k):
    if 0 <= k <= n:
        ntok = 1
        ktok = 1
        for t in range(1, min(k, n - k) + 1):
            ntok *= n
            ktok *= t
            n -= 1
        return ntok // ktok
    else:
        return 0

def powerOfK(k, max):
    if k == 1:
        return [1]
    if k == -1:
        return [-1, 1]

    result = []
    n = 1
    while n <= max:
        result.append(n)
        n *= k
    return result

def divisors(n):
    i = 1
    result = []
    while i*i <= n:
        if n%i == 0:
            if n/i == i:
                result.append(i)
            else:
                result.append(i)
                result.append(n/i)
        i+=1
    return result

# @lru_cache(maxsize=None)
def digitsSum(n):
    if n == 0:
        return 0
    r = 0
    while n > 0:
        r += n % 10
        n //= 10
    return r

######################
# ---- GRID Fns ---- #
######################
def isValid(i, j, n, m):
    return i >= 0 and i < n and j >= 0 and j < m

def print_grid(grid):
    for line in grid:
        print(" ".join(map(str,line)))

######################
# ---- MISC Fns ---- #
######################
def kadane(a,size):
    max_so_far = 0
    max_ending_here = 0

    for i in range(0, size):
        max_ending_here = max_ending_here + a[i]
        if (max_so_far < max_ending_here):
            max_so_far = max_ending_here

        if max_ending_here < 0:
            max_ending_here = 0
    return max_so_far

def prefixSum(arr):
    for i in range(1, len(arr)):
        arr[i] = arr[i] + arr[i-1]
    return arr

def ceil(n, d):
    if n % d == 0:
        return n // d
    else:
        return (n // d) + 1

# INPUTS  --------------------------
# s = input().decode('utf-8').strip()
# n = int(input())
# l = list(map(int, input().split()))
# t = int(input())
# for _ in range(t):
# for _ in range(t):

def solve(arr1, arr2, p, t):
    if not len(arr1) or not len(arr2):
        return 1

    i, j = 0, 0
    cnt = 1
    # p = arr1[0]
    # t = True
    while i < len(arr1) and j < len(arr2):
        if t:
            while j < len(arr2) and arr2[j] <= p:
                j += 1
            if j < len(arr2):
                p = arr2[j]
                t = not t
                cnt += 1
        else:
            while i < len(arr1) and arr1[i] <= p:
                i += 1
            if i < len(arr1):
                p = arr1[i]
                t = not t
                cnt += 1

    if t and j < len(arr2):
        while j < len(arr2) and arr2[j] <= p:
            j += 1
        if j < len(arr2):
            p = arr2[j]
            t = not t
            cnt += 1
    elif not t and i < len(arr1):
        while i < len(arr1) and arr1[i] <= p:
            i += 1
        if i < len(arr1):
            p = arr1[i]
            t = not t
            cnt += 1

    return cnt

n = int(input())
l = list(map(int, input().split()))
if n <= 2:
    print(n)
    exit()

best = 0
m = collections.defaultdict(list)
for i, v in enumerate(l):
    m[v].append(i)

keys = list(m.keys())
for i in range(len(keys)):
    for j in range(i+1, len(keys)):

        arr1 = m[keys[i]]
        arr2 = m[keys[j]]
        if len(arr1) + len(arr2) <= best:
            continue
            
        r = solve(arr1, arr2, arr1[0], True)
        best = max(r, best)
        r2 = solve(arr1, arr2, arr2[0], False)
        best = max(r2, best)
        best = max(best, len(arr1))
        best = max(best, len(arr2))

print(best)
