B. Фибионаччийн дэд хэсэг

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $a_1, a_2, ... , a_n$ массив өгөгдсөн. $[l, r]$ ($1 ≤ l < r ≤ n$) дэд хэсгийн ($l + 2 ≤ i ≤ r$) байх бүх $i$-ийн хувьд $a_i=a_i-1+a_i-2$ байвал “сайн дэд хэсэг” болно.

$len([l, r])$ = $r - l + 1$ гэж тодорхойлъё. $len([l, r])$ нь дэд хэсэг $[l, r]$-ийн урт юм. Хэрэв $len([l_1, r_1]) > len([l_2, r_2])$ бол дэд хэсэг $[l_1, r_1]$ нь дэд хэсэг $[l_2, r_2]$-ээс урт байна.

Таны даалгавар бол $a$ массив дахь хамгийн урт “сайн дэд хэсэг”-ийг олох юм. 1 эсвэл 2 урттай дэд хэсгүүд ямагт сайн байдгийг анхаараарай.

Оролт

Эхний мөрөнд массивийн элементүүдийн тоо болох ганц бүхэл тоо $n$ ($1 ≤ n ≤ 10^5$) байна. Хоёр дахь мөрөнд $a_1, a_2, ... , a_n$ ($0 ≤ a_i ≤ 10^9$) бүхэл тоонууд байна.

Гаралт

A массив дахь хамгийн урт “сайн дэд хэсэг”-ийн уртыг хэвлэнэ.

Орчуулсан: Энхдүүрэн

Жишээ тэстүүд

Оролт
10
1 2 3 5 8 13 21 34 55 89
Гаралт
10
Оролт
5
1 1 1 1 1
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...