Аморальні екcперименти

Limits: 2 sec., 256 MiB

Щоб розробити ефективну вакцину від реп’яховірусу, потрібно розуміти, наскільки швидко він розповсюджується. Провідні українські вчені — Зеник та Марічка — проводять різноманітні експерименти, щоб краще розуміти закономірності розповсюдження вірусу.

Цього разу вони розсадили \(n\) людей за круглим столом. Для кожної людини відомо, чи вона заражена на початку експерименту. Зеник припускає, що якщо людина хвора, то рівно за одну хвилину вона заражає людей, що сидять поряд з нею за столом.

Якщо припущення Зеника правильне, то через скільки часу всі люди за столом будуть зараженими?

Input

У першому рядку задано ціле число \(n\) — кількість людей, що беруть участь в експерименті.

У другому рядку задано \(n\) чисел 0 або 1. 1 означає, що відповідний учасник експерименту є хворим на початку експерименту, 0 — здоровим.

Output

У єдиному рядку виведіть ціле число — мінімальний час, через який усі учасники експерименту захворіють, якщо припущення Зеника є правильним.

Constraints

\(1 \le n \le 10^5\),

на початку експерименту є щонайменше один заражений учасник.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 1 0 0 0 1 0 1	2

Notes

Після першої хвилини лише третій учасник буде здоровим, після другої — усі заражені.