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;
}

總結

以上是生活随笔為你收集整理的Almost Arithmetical Progression的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。