← 返回题目列表

Codeforces · 255/C

C. 几乎算术级数

中文机器翻译题面 查看原题

Gena 喜欢数字序列。最近,他发现了一种新型序列,他称之为几乎算术级数。如果序列的元素可以表示为:

- a1 = p,其中 p 是某个整数;
- ai = ai - 1 + ( - 1)i + 1·q (i > 1),其中q是某个整数。

现在 Gena 有一张纸,序列为 b,由 n 个整数组成。帮助 Gena,找到最长的整数子序列,它几乎是算术级数。

序列 s1, s2, ..., sk 是序列 b1, b2, ..., bn 的子序列,如果存在索引 i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n) 的递增序列,则 bij = sj。换句话说,从b中删除一些元素就可以得到序列s。

输入

第一行包含整数 n (1 ≤ n ≤ 4000)。下一行包含 n 个整数 b1, b2, ..., bn (1 ≤ bi ≤ 106)。

输出

打印单个整数 — 所需的最长子序列的长度。

示例

输入 #1

2
3 5

输出 #1

2

输入 #2

4
10 20 10 30

输出 #2

3

注意

在第一个测试中,该序列实际上是合适的子序列。

在第二个测试中,以下子序列适合:10, 20, 10。