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。