Яаш саяхан Фибоначч-ийн дараалал үзсэн бөгөөд үүний талаар ихээхэн сонирхож байгаа юм. Тэрээр аливаа дарааллыг дараах нөхцөлийг хангаж байвал Фибоначчи-иш гэж нэрлэж байв. Үүнд:

1. Дараалал нь дор хаяж 2 элементээс тогтоно.
2. $f_{0}$ болон $f_{1}$-ыг дураараа сонгоно.
3. Бүх $n ≥ 0$-ын хувьд $f_{n + 2} = f_{n + 1} + f_{n}$ байна.

Танд бүхэл тоон дараалал $a_{1}, a_{2}, ..., a_{n}$ өгөгдөв. Таны даалгавар бол уг дарааллын элементүүдээс сонгож боломжит хамгийн урт Фибоначчи-иш дараалал үүсгэх явдал юм.

Оролт

Эхний мөрөнд $a_{i}$ дарааллын урт болох ганц бүхэл тоо $n$ ($2 ≤ n ≤ 1000$) өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ ($|a_{i}| ≤ 10^{9}$)-ууд өгөгдөнө.

Гаралт

Дахин байрлуулсны дараах дараалалд байх боломжит хамгийн урт Фибоначчи-иш дарааллын уртыг хэвлэнэ.

Эхний жишээнд хэрэв бид дарааллаа $-1$, $2$, $1$ гэж дахин байрлуулбал $a_{i}$ дараалал нь тэр чигээрээ Фибоначчи-иш дараалал болох юм.

2-дахь жишээнд, оновчтой боломжит хувилбар нь дараах байдлаар байх юм. , , , , $28$.