Яш недавно узнал о числах Фибоначчи. Он так обрадовался этому знанию, что решил называть произвольную последовательность фибоначчиеватой, если
- последовательность состоит хотя бы из двух элементов;
- f0 и f1 произвольные;
- fn + 2 = fn + 1 + fn при всех n ≥ 0.
Вам дана последовательность целых чисел a1, a2, ..., an. Вам требуется переставить элементы последовательности таким образом, чтобы как можно более длинный её префикс был фибоначчиеватой последовательностью.
Выходные данные
Выведите количество элементов в самом длинном возможном фибоначчиеватом префиксе после перестановки элементов.
Примечание
В первом примере, если переставить элементы исходной последовательности следующим образом - 1, 2, 1, то вся последовательность ai будет фибоначчиеватой.
Во втором примере оптимальным способом переставить элементы является 
, 
, 
, 
, 28.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 -1
|
3
|
|
2
|
5
28 35 7 14 21
|
4
|