Емма və qəribə dairə#10222
Dünyanın ən nüfuzlu kino mükafatlarından birini qazandıqdan sonra Emma çox qeyri-adi bir hədiyyə aldı — sektorlara bölünmüş bir dairə. Dairənin cüt sayda sektoru var, bu say ilə göstərilib. Bəzi sektorlarda daşlar var, digərləri isə boşdur.
Emma gördü ki, daşları yalnız birbaşa qarşı tərəfdəki sektora köçürə bilər. Lakin, bir sektorda iki daş yerləşdirmək mümkün deyil (niyə və necə olduğunu soruşmayın — bu bir sehirdir). Mükafat təqdimatından sonrakı ziyafət çox darıxdırıcı olduğu üçün Emma qərar verdi: görəsən daşlarla dolu olan ardıcıl sektorların maksimal uzunluğu nə qədər ola bilər?
Emma aktrisadır, odur ki, sizin tapşırığınız — bu tapmacada ona kömək etməkdir.
Daşların köçürülməsi qaydalarını xatırladaq:
Daşı yalnız birbaşa qarşıdakı sektora köçürmək olar.
Bir sektorda birdən çox daş ola bilməz.
Daha yaxşı anlamaq üçün, şəkildə birinci nümunə üçün daşların köçürülməsinin mümkün variantlarından biri göstərilmişdir.
Birinci sətirdə bir tam ədəd verilir. İkinci sətirdə ədəd — və ya ( sektorda daş var deməkdir, isə sektorun boş olduğunu göstərir) verilir. 1 \leq n \leq 10^6. cüt ədəddir. Ən azı bir boş sektor mövcuddur.
Cavab olaraq — əldə edilə bilən ən uzun sehrli (ardıcıl dolu) sektorların uzunluğunu göstərən bir tam ədəd çap edin.
Nümunə 1
Nümunə 2