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: MEDIUM
Tags: Dynamic programming

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
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)


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
		xi = get_len(d[x], d[y])
		ans = max(ans, xi)
ans1 = [len(d[e]) for e in d]
ans = max(ans, max(ans1))
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
ans = 1
arr = [int(x) for x in input().split()]
for i in range(n):
	temp = set()
	d = {}
	for j in range(i + 1, n):
		if arr[j] == arr[i]:
			temp = set()
		elif arr[j] not in temp:
			if arr[j] in d:
				d[arr[j]] += 1
			else:
				d[arr[j]] = 1
			temp.add(arr[j])
	number = -1
	maxi = -1
	for i in d:
		if maxi < d[i]:
			number = i
			maxi = d[i]
	if number in temp:
		ans = max(ans, 2 * maxi)
	else:
		ans = max(ans, 2 * maxi + 1)
d = {}
for i in arr:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
for i in d:
	ans = max(ans, d[i])
print(ans)


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)


import sys
input = sys.stdin.readline
a = int(input())
z = list(map(int, input().split()))
from collections import *
from bisect import *
dp = [[0 for i in range(len(z))] for i in range(len(z))]
for i in range(len(z)):
	dp[0][i] = 1
al = defaultdict(list)
maxa = 0
for i in range(len(z)):
	al[z[i]].append(i)
	maxa = max(maxa, len(al[z[i]]))
for i in range(len(z)):
	index = -1
	for j in range(i):
		if z[i] != z[j]:
			if index == -1:
				dp[i][j] = max(2, dp[i][j])
			else:
				dp[i][j] = max(dp[i][j], dp[j][index] + 1)
		else:
			index = j
		maxa = max(dp[i][j], maxa)
print(maxa)


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)


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()


(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
from math import log2, floor, ceil, sqrt
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)


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict

def solve(x, y):
	(j, l, ma) = (len(x) - 1, 0, -1)
	for i in range(len(y) - 1, -1, -1):
		if y[i] > ma:
			l += 1
			while j > -1 and x[j] < y[i]:
				j -= 1
			if j == -1:
				break
			ma = x[j]
			l += 1
	return l

def main():
	n = int(input())
	b = list(map(int, input().split()))
	a = sorted(set(b))
	(c, z) = ({}, 0)
	for i in a:
		z += 1
		c[i] = z
	for i in range(n):
		b[i] = c[b[i]]
	a = defaultdict(list)
	for i in range(n - 1, -1, -1):
		a[b[i]].append(i)
	b = list(range(1, z + 1))
	maxdist = b[-1]
	(ma, l) = (len(a[max(a, key=lambda x: len(a[x]))]), len(b))
	for dist in range(1, maxdist):
		for j in range(l):
			i = b[j]
			if i + dist <= maxdist:
				(z, y) = (a[i], a[i + dist])
				if len(z) + len(y) > ma:
					ma = max(ma, solve(z, y), solve(y, z))
			else:
				l = j
				break
	print(ma)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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]]
for i in range(n):
	for j in range(i):
		dp[i][b[j]] = max(dp[j][b[i]] + 1, dp[i][b[j]])
ans = 0
for l in dp:
	ans = max(ans, max(l))
print(ans)


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)
	pass

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

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

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

def find_next(l, li, i):
	while l[li] < i:
		li += 1
		if li == len(l):
			return -1
	return li
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)):
	ii = index[i]
	for j in range(len(index)):
		jj = index[j]
		if i == j:
			max_cnt = max(max_cnt, len(index[i]))
			continue
		pi = 0
		pj = 0
		ij = 0
		cnt = 1
		while True:
			if ij == 0:
				tmp = find_next(jj, pj, ii[pi])
				if tmp == -1:
					break
				pj = tmp
				cnt += 1
				ij = 1
			else:
				tmp = find_next(ii, pi, jj[pj])
				if tmp == -1:
					break
				pi = tmp
				cnt += 1
				ij = 0
		max_cnt = max(max_cnt, cnt)
print(max_cnt)


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)


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)


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)
	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
			elif jl[cj] < il[ci]:
				cnt += 1
				ij = 'i'
			else:
				ci += 1
		max_cnt = max(max_cnt, cnt)
print(max_cnt)


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, input().split()))

def fn(a):
	mp = {}
	b = []
	cnt = 0
	for v in a:
		if v in mp:
			b += [mp[v]]
		else:
			b += [cnt]
			mp[v] = cnt
			cnt += 1
	return b
for i in range(1):
	n = nmbr()
	a = fn(lst())
	N = max(a) + 1
	ans = 1
	dp = [[1 for _ in range(N)] for j in range(n)]
	for i in range(1, n):
		for j in range(i):
			dp[i][a[j]] = 1 + dp[j][a[i]]
			ans = max(ans, dp[i][a[j]])
	print(ans)


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)


import os, sys
from io import BytesIO, IOBase
from collections import defaultdict

def main():
	n = int(input())
	b = list(map(int, input().split()))
	ls = defaultdict(lambda : -1)
	dp = [[1] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			z = ls[b[j]]
			if z != -1:
				dp[i][j] = dp[z][i] + 1
		ls[b[i]] = i
	print(max(map(max, dp)))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os, io
from sys import stdout
import collections
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

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

def digitsSum(n):
	if n == 0:
		return 0
	r = 0
	while n > 0:
		r += n % 10
		n //= 10
	return r

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

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

def solve(arr1, arr2, p, t):
	if not len(arr1) or not len(arr2):
		return 1
	(i, j) = (0, 0)
	cnt = 1
	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)