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。