Piramidanın aşağısına doğru

Ədədi piramidalarla maraqlanırsınızmı? Əsas ardıcıllıq verilərkən, adətən, piramidanın qalan hissəsini aşağıdan yuxarıya doğru qurmaq lazımdır: hər bir qonşu ədədlər cütü üçün onların cəmini hesablayaraq yuxarıya yazmalısınız. Məsələn, $[1,2,3]$ əsas ardıcıllığı üçün yuxarıdakı ardıcıllıq $[3,5]$ olacaq və piramidanın zirvəsi $[8]$ olacaq:

Lakin mən piramidanı tamamlamaqdan çox, yerin altına getməyi üstün tuturam. Beləliklə, $n$ qeyri-mənfi tam ədədlərdən ibarət ardıcıllıq üçün onun altında $n+1$ qeyri-mənfi tam ədədlərdən ibarət ardıcıllıq yazacağam ki, başlanğıc ardıcıllığındakı hər bir ədəd onun altında yerləşdirdiyim iki ədədin cəmi olsun. Bu şərti ödəyən bir neçə mümkün ardıcıllıq ola bilər və ya heç biri olmaya bilər. Mənə neçə ardıcıllıqdan seçim edə biləcəyimi deyə bilərsinizmi?

Giriş verilənləri

Birinci sətirdə əsas ardıcıllığın uzunluğu $n(1\le n\le 10^6)$ verilir.

Növbəti sətirdə $n$ tam ədəd $a_1,...,a_n(0\le a_i\le 10^8$ hər bir $i$ üçün) — əsas ardıcıllıq verilir.

Çıxış verilənləri

Giriş ardıcıllığının ədədi piramidanın növbəti səviyyəsi olacağı neçə qeyri-mənfi tam ədədlər ardıcıllığının olduğunu çıxarın.

Nümunələr