Almost Arithmetical Progression

Description

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₁ = 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₁,  s₂,  ...,  s_k is a subsequence of sequence b₁,  b₂,  ...,  b_n, if there is such increasing sequence of indexesi₁, i₂, ..., i_k(1  ≤  i₁  <  i₂  < ...   <  i_k  ≤  n), that b_ij  =  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₁, b₂, ..., b_n(1 ≤ b_i ≤ 10⁶).

Output

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

Sample Input

Input 2 3 5 Output 2 Input 4 10 20 10 30 Output 3

Hint

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

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

/*求最长的子序列，满足隔位的两个数相等*/ #include <cstdio> #include <algorithm> using namespace std; const int MAXN = 4000 + 10; int n; int b[MAXN]; int dp[MAXN][MAXN];//定义状态dp[i][j]代表以第i个数为末尾，第j个数为倒数第二个的情况下的最长子序列。 int main() {     while (scanf("%d", &n) == 1)     {       for (int i = 1; i <= n; ++i)     {         scanf("%d", &b[i]);     }     int ret = 0;     dp[0][0] = 0;     for (int j = 1; j <= n; ++j)     {         for (int i = 0, last = 0; i < j; ++i)         {             dp[i][j] = dp[last][i] + 1;             if (b[i] == b[j])             {                 last = i;             }             ret = max(ret, dp[i][j]);         }     }     printf("%d\n", ret);     }     return 0; }