Almost Arithmetical Progression

题意翻译

## 题目描述： 先给出一个整数 $n$ ,再给出一个有 $n$ 个元素的序列 $b$。 现在要你求序列 $b$ 中最长的子序列，满足隔位的两个数相等，问这个最长的子序列的长度是多少。 ## 输入格式 一个整数$n$ ($1\le n\le4000$) 和一串序列 $b_1,b_2,......,b_n$($1\le b_i\le10^ 6$)。 ## 输出格式 一个整数，表示这个最长的子序列的长度。

题目描述

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&gt;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}&lt;i_{2}&lt;...\ &lt;i_{k}<=n) $ , that $ b_{ij}=s_{j} $ . In other words, sequence $ s $ can be obtained from $ b $ by crossing out some elements.

输入输出格式

输入格式

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}) $ .

输出格式

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

输入输出样例

输入样例 #1

2
3 5

输出样例 #1

2

输入样例 #2

4
10 20 10 30

输出样例 #2

3

说明

In the first test the sequence actually is the suitable subsequence. In the second test the following subsequence fits: $ 10,20,10 $ .