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:  a_1 = p, where p is some integer;  a_{i} = a_{i} - 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 s_1,  s_2,  ...,  s_{k} is a subsequence of sequence b_1,  b_2,  ...,  b_{n}, if there is such increasing sequence of indexes i_1, i_2, ..., i_{k} (1  ≤  i_1  <  i_2  < ...   <  i_{k}  ≤  n), that b_{i}_{j}  =  s_{j}. 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 b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 10^6).


-----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.

Difficulty: interview

Starter code:

Solutions:
d, n, t = 0, int(input()), list(map(int, input().split()))
p = {a: 0 for a in set(t)}
for i in range(n):
    a = t[i]
    if not a in p: continue
    p.pop(a)
    s = t.count(a) - 1
    if 2 * s < d: continue
    if s > d: d = s
    k = i + 1
    for j in range(k, n):
        if t[j] == a:
            for b in set(t[k: j]):
                if b in p: p[b] += 2
            k = j + 1
    for b in set(t[k: n]):
        if b in p: p[b] += 1
    for b in p:
        if p[b] > d: d = p[b]
        p[b] = 0
print(d + 1)

d, n, t = 0, int(input()), list(map(int, input().split()))
p = {a: 0 for a in set(t)}
for i in range(n):
    a = t[i]
    if not a in p: continue
    p.pop(a)
    s = t.count(a) - 1
    if 2 * s < d: continue
    if s > d: d = s
    k = i + 1
    for j in range(k, n):
        if t[j] == a:
            for b in set(t[k: j]):
                if b in p: p[b] += 2
            k = j + 1
    for b in set(t[k: n]):
        if b in p: p[b] += 1
    for b in p:
        if p[b] > d: d = p[b]
        p[b] = 0
print(d + 1)

n = int(input())
a = list(map(int, input().split()))
dp=[[0 for i in range(n+1)] for i in range(n+1)]
ans = 0
pre = 0
a = [0] + a
for i in range(1, n+1):
    pre = 0
    for j in range(i):
        dp[i][j] = dp[j][pre]+1
        if a[i] == a[j]:
            pre = j
        ans = max(ans, dp[i][j])
print(ans)

n = int(input())
a = list(map(int, input().split()))
dp=[[0 for i in range(n+1)] for i in range(n+1)]
ans = 0
pre = 0
a = [0] + a
for i in range(1, n+1):
    pre = 0
    for j in range(i):
        dp[i][j] = dp[j][pre]+1
        if a[i] == a[j]:
            pre = j
        ans = max(ans, dp[i][j])
print(ans)

d, n, t = 0, int(input()), list(map(int, input().split()))

p = {a: 0 for a in set(t)}

for i in range(n):

    a = t[i]

    if not a in p: continue

    p.pop(a)

    s = t.count(a) - 1

    if 2 * s < d: continue

    if s > d: d = s

    k = i + 1

    for j in range(k, n):

        if t[j] == a:

            for b in set(t[k: j]):

                if b in p: p[b] += 2

            k = j + 1

    for b in set(t[k: n]):

        if b in p: p[b] += 1

    for b in p:

        if p[b] > d: d = p[b]

        p[b] = 0

print(d + 1)



# Made By Mostafa_Khaled


R = lambda: map(int, input().split())
n = int(input())
arr = list(R())
dp = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
    p = -1
    for j in range(i):
        dp[i][j] = max(dp[i][j], dp[j][p] + 1)
        p = j if arr[j] == arr[i] else p
print(max(max(dp[i]) for i in range(n)) + 1)

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
        


d, n, t = 0, int(input()), list(map(int, input().split()))
p = {a: 0 for a in set(t)}
for i in range(n):
    a = t[i]
    if not a in p: continue
    p.pop(a)
    s = t.count(a) - 1
    if 2 * s < d: continue
    if s > d: d = s
    k = i + 1
    for j in range(k, n):
        if t[j] == a:
            for b in set(t[k: j]):
                if b in p: p[b] += 2
            k = j + 1
    for b in set(t[k: n]):
        if b in p: p[b] += 1
    for b in p:
        if p[b] > d: d = p[b]
        p[b] = 0
print(d + 1)

import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def solve():
	n = mint()
	a = [None]*n
	i = 0
	for v in mints():
		a[i] = (v, i) 
		i += 1
	a.sort()
	i = 0
	r = 0
	while i < n:
		j = i + 1
		x = a[i][0]
		while j < n and a[j][0] == x:
			j += 1
		r = max(r, j-i)
		ni = j
		while j < n:
			jj = j
			y = a[j][0]
			ii = i
			if a[ii][1] < a[jj][1]:
				cnt = 1
				left = a[ii][1]
				ii += 1
			else:
				cnt = 0
				left = -1
			fail = False
			while True:
				while True:
					if jj >= n or a[jj][0] != y:
						fail = True
						break
					if a[jj][1] > left:
						left = a[jj][1]
						cnt += 1
						jj += 1
						break
					jj += 1
				if fail:
					break
				while True:
					if ii >= ni:
						fail = True
						break
					if a[ii][1] > left:
						left = a[ii][1]
						cnt += 1
						ii += 1
						break
					ii += 1
				if fail:
					break
			r = max(r, cnt)
			while jj < n and a[jj][0] == y:
				jj += 1
			j = jj
		i = ni
	print(r)

solve()


import sys
from math import log2,floor,ceil,sqrt
# import bisect
# from collections import deque

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

n = int(ri())
arr = Ri()
a = sorted(arr)
dic = {}
ite = 1
for i in range(n):
    if a[i] not in dic:
        dic[a[i]] = ite
        ite+=1
for i in range(n):
    arr[i] = dic[arr[i]]
dp = list2d(n,n+1,0)
for i in range(n):
    for j in range(n+1):
        dp[i][j] = 1
maxx = 1
for i in range(1,n):
    for j in range(i-1,-1,-1):
        dp[i][arr[j]] = max(dp[i][arr[j]], dp[j][arr[i]]+1)
        maxx = max(maxx,dp[i][arr[j]])
print(maxx)






n = int(input())
ls = list(map(int, input().split()))
dp = [[1 for i in range(n)] for j in range(n)]
laspos = [None] * (max(ls) + 1)
for i in range(n):
	for j in range(i):

		if laspos[ls[i]] is not None:
			dp[i][j] = 1 + dp[j][laspos[ls[i]]]
		else:
			dp[i][j] += 1
		laspos[ls[j]] = j

mx = -100000
for i in range(n):
	for j in range(n):
		mx = max(dp[i][j], mx)
print(mx)


def function(n , array):
    grid = [ {} for i in range(n)]

    if(n <= 2):
        print(n)
        return

    global_max = -10
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            diff = array[i] - array[j]

            max_val = 1
            if((-diff) in grid[j].keys()):
                max_val = max(grid[j][(-diff)] + 1, max_val)

            if(diff in grid[i].keys()):
                max_val = max(max_val, grid[i][diff])
                grid[i][diff] = max_val
            else:
                grid[i][diff] = max_val

            global_max = max(global_max, max_val)

    print(global_max + 1)

n = int(input())
array = [ int(x) for x in input().split() ]
function(n, array)

# WHY IS RUBY SO SLOW????
input()
a=[*list(map(int,input().split()))]
r={}
for i, x in enumerate(list(set(a))):
	r[x] = i
n = len(r)
m = 0
a = [r[x] for x in a]
for i,x in enumerate(a):
	h=[0 for _ in range(n)]
	l=[-2 for _ in range(n)]
	lx = -1
	for j,y in enumerate(a[i+1:]):
		if y == x:
			lx = j
		if l[y] < lx:
			h[y] += 1
		l[y] = j
	for k in range(n):
		if k == x:
			h[k] = h[k] + 1
		elif l[k] < lx:
			h[k] = 2*h[k] + 1
		else:
			h[k] = 2*h[k]
	m = max(m, max(h+[1]))
print(m)


n=int(input())
b=list(map(int,input().split()))
dp=[[1]*n for i in range(n)]
d,k={},0
for i in range(n):
	if b[i] not in d:
		d[b[i]]=k
		k+=1
	b[i]=d[b[i]]
d.clear()
for i in range(n):
	for j in range(i):
		dp[i][b[j]]=max(1+dp[j][b[i]],dp[i][b[j]])
ans=0
for l in dp:
	ans=max(ans,max(l))
print(ans)

#!/usr/bin/env python3
from sys import stdin
    
    
def solve(tc):
    n = int(stdin.readline().strip())
    seq = list(map(int, stdin.readline().split()))
    
    elems = []
    idxcnt = 0
    idx = dict()
    for i in range(n):
        if seq[i] not in idx:
            idx[seq[i]] = idxcnt
            idxcnt += 1
            elems.append([])
        elems[idx[seq[i]]].append(i)
    
    ans = 1
    for li in elems:
        ans = max(ans, len(li))
    
    m = len(elems)
    for i in range(m):
        for j in range(m):
            if i == j:
                continue
            cur = -1
            cnt = 0
            leni, lenj = len(elems[i]), len(elems[j])
            pi, pj = 0, 0
            while True:
                while pi<leni and elems[i][pi]<cur:
                    pi += 1

                if pi == leni:
                    break
                cur = elems[i][pi]
                cnt += 1
                pi += 1

                while pj<lenj and elems[j][pj]<cur:
                    pj += 1

                if pj == lenj:
                    break
                cur = elems[j][pj]
                cnt += 1
                pj += 1
            ans = max(ans, cnt)
    
    print(ans)
    
    
tc = 1
solve(tc)