CF255C.Almost Arithmetical Progression

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.

杰纳喜欢数字序列。最近，他发现了一种新型序列，并将其称为“准等差数列”。若一个序列的元素可表示为：

• $a_1 = p$，其中 $p$ 为某个整数；
• $a_i = a_{i-1} + (-1)^{i+1} \cdot q$（当 $i > 1$ 时），其中 $q$ 为某个整数，

则该序列为一个准等差数列。

目前，杰纳有一张写有长度为 $n$ 的整数序列 $b$ 的纸。请帮助杰纳找出其中最长的子序列，使其构成一个准等差数列。

序列 $s_1,\ s_2,\ \dots,\ s_k$ 是序列 $b_1,\ b_2,\ \dots,\ b_n$ 的一个子序列，当且仅当存在一个严格递增的下标序列 $i_1,\ i_2,\ \dots,\ i_k$（满足 $1 \le i_1 < i_2 < \dots < i_k \le n$），使得对所有 $j = 1,2,\dots,k$ 都有 $b_{i_j} = s_j$。换言之，序列 $s$ 可通过对序列 $b$ 删除若干元素而得到。

The first line contains integer n (1 ≤ n ≤ 4000). The next line contains n integers _b_1, _b_2, ..., b__n (1 ≤ b__i ≤ 106).

第一行包含一个整数 $n$（$1 \leq n \leq 4000$）。下一行包含 $n$ 个整数 $b_1, b_2, ..., b_n$（$1 \leq b_i \leq 10^6$）。

Print a single integer — the length of the required longest subsequence.

输出一个整数——所求最长子序列的长度。

In the first test the sequence actually is the suitable subsequence.

In the second test the following subsequence fits: 10, 20, 10.

在第一个测试用例中，该序列本身就是合适的子序列。

在第二个测试用例中，以下子序列满足条件：10, 20, 10。