Задача G. Great array ≡

Условие

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

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

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

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

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

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

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

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

В следующих n строках записано n целых чисел a₁,a₂,...,a_n (|a_i| ≤ 10⁹).

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

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

Ограничения

2 ≤ n ≤ 1000

|a_i| ≤ 10⁹

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

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

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

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

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

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

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

5
5
2
3
1
-1

4