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