← 返回题目列表

Codeforces · 633/D

D. 斐波那契式

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

Yash 最近了解了斐波那契数列,对此感到非常兴奋。他称一个序列为斐波那契式如果

1.序列至少由两个元素组成
2. f0和f1是任意的
3. 对于所有 n ≥ 0,fn + 2 = fn + 1 + fn。

给定一些整数序列 a1, a2, ..., an。您的任务是重新排列该序列的元素,使其最长的可能前缀成为斐波那契序列。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 1000) — 序列 ai 的长度。

第二行包含 n 个整数 a1, a2, ..., an (|ai| ≤ 109)。

输出

打印重新排列后给定序列的最长可能斐波那契前缀的长度。

示例

输入 #1

3
1 2 -1

输出 #1

3

输入 #2

5
28 35 7 14 21

输出 #2

4

注意

在第一个示例中,如果我们将序列的元素重新排列为 - 1, 2, 1,则整个序列 ai 将是斐波那契式的。

在第二个示例中,重新排列元素的最佳方式是 $$7$$、$$14$$、$$21$$、$$35$$、28。