Gizli Ağac
İkili ağacın yarpaqlarına tam ədədlər təyin edilib. Belə bir ağac, hər bir yarpaq olmayan düyün üçün sol alt ağacındakı ağırlıqların cəmi sağ alt ağacındakı ağırlıqların cəminə bərabər olduqda balanslı adlanır. Məsələn, aşağıdakı şəkildəki ağac balanslıdır.
Şəkil 1. Balanslı ağac
Balanslı ağac A ardıcıllığında gizli sayılır, əgər ağacın bütün yarpaqlarının ağırlıqlarını soldan sağa sıralamaqla əldə edilən tam ədədlər ardıcıllığın alt ardıcıllığını təşkil edirsə. Burada, alt ardıcıllıq orijinal ardıcıllıqdan sıfır və ya daha çox elementi silməklə və qalan elementlərin sırasını dəyişmədən əldə edilən ardıcıllıqdır.
Məsələn, yuxarıdakı şəkildəki balanslı ağac 3 4 1 3 1 2 4 4 6 ardıcıllığında gizlidir, çünki 4 1 1 2 4 4 onun alt ardıcıllığıdır.
İndi sizin vəzifəniz verilmiş tam ədəd ardıcıllığında gizli olan ən çox yarpağa malik balanslı ağacı tapmaqdır. Əslində, Şəkil 1-də göstərilən ağac yuxarıda qeyd olunan ardıcıllıqda gizli olan balanslı ağaclar arasında ən çox yarpağa malikdir.
Giriş verilənləri
Giriş bir neçə datasetdən ibarətdir. Hər bir dataset A tam ədəd ardıcıllığını aşağıdakı formatda təqdim edir:
N
A_1 A_2 ... A_N
burada 1 ≤ N ≤ 1000 və 1 ≤ A_i ≤ 500 üçün 1 ≤ i ≤ N. N giriş ardıcıllığının uzunluğudur və A_i ardıcıllığın i-ci elementidir.
Giriş bir tək sıfırdan ibarət olan sətirlə bitir. Datasetlərin sayı 50-dən çox deyil.
Çıxış verilənləri
Hər bir dataset üçün A ardıcıllığında gizli olan ən çox yarpağa malik balanslı ağacı tapın və onun yarpaqlarının sayını bir sətirdə çıxış edin.