Емма və qəribə dairə
Məşhur kino mükafatlarından birində qalib gəldikdən sonra Emma çox maraqlı bir hədiyyə aldı - sektorlara bölünmüş bir dairə. Bu dairə ümumilikdə cüt sayda sektordan ibarətdir - n. Bəzi sektorlarda daş var, bəziləri isə boşdur.
Emma müşahidə etdi ki, daşları yalnız əks sektorlara köçürə bilər. Hər sektorda yalnız bir daş ola bilər (niyə və necə olduğunu soruşmayın, bu bir sehrdir). Kino mükafatının təqdimatından sonrakı ziyafət olduqca darıxdırıcı olduğu üçün Emma, daşlarla dolu sektorlardan ibarət olan ən uzun ardıcıllığın uzunluğunu öyrənmək istədi.
Emma aktrisadır, buna görə də sizin vəzifəniz ona bu məsələdə kömək etməkdir.
Köçürmə qaydalarını xatırladaq:
Daşı yalnız əks sektora köçürmək olar.
Hər sektorda bir daşdan çox ola bilməz.
Daha yaxşı başa düşmək üçün, şəkildə birinci test nümunəsində daşların köçürülməsinin bir variantı göstərilmişdir.
Giriş məlumatları
Birinci sətirdə bir tam ədəd n verilir. Növbəti sətirdə n ədəd 0 və ya 1 (1 - sektorda daş var, 0 - sektor boşdur) verilir. 1 <= n <= 10^6.n - cüt ədəddir. Ən azı bir boş sektor mövcuddur.
Çıxış məlumatları
Bir tam ədəd, məsələnin cavabı - ən uzun sehrli ardıcıllığın uzunluğu.