Задача G. Great array

Автор:Денис Лысенко   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Тимоше нравятся числа Фибоначчи настолько, что он решил называть последовательности, которое похожи на числа Фибоначчи, красивыми. Тимоша посчитает ряд красивым, если:

1. Последовательность состоит не менее чем из двух элементов.

2. Первое и второе число последовательности могут быть любыми.

3. Каждый последующий элемент последовательности равен сумме двух предыдущих (за исключением первых двух элементов).

Тимоша записал на доске ряд чисел f1,f2,...,fn. Тимоша хочет сделать ряд красивым и для этого может переставлять местами любые элементы. Однако, Тимоша знает, что случайно написанные числа вряд ли станут красивой последовательностью, поэтому он решает находить красивые подпоследовательности.

Помогите Тимоше и ответьте - какой максимальной длины может получится красивая подпоследовательность после перестановки элементов.

Формат входных данных

В первой строке записано единственное число n (2 ≤ n ≤ 1000) — длина последовательности fi.

В следующих n строках записано n целых чисел a1,a2,...,an (|ai| ≤ 109).

Формат выходных данных

Выведите количество элементов в самой длинной красивой подпоследовательности после перестановки элементов.

Ограничения

2 ≤ n ≤ 1000

|ai| ≤ 109

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения
nai
1102 ≤ n ≤ 10|ai| ≤ 100
2352 ≤ n ≤ 100|ai| ≤ 105
3552 ≤ n ≤ 1000|ai| ≤ 109

Пояснение к примерам

В примере если переставить как  − 12135, то подпоследовательность  − 1213 станет красивой

Примеры тестов

Стандартный вход Стандартный выход
1
5
5
2
3
1
-1
4

0.081s 0.009s 13