Immoral Experiments

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

To develop an effective vaccine against the burdock virus, it is necessary to understand how fast it spreads. Leading Ukrainian scientists — Zenik and Marichka — are conducting various experiments to better understand the patterns of virus propagation.

This time, they seated \(n\) people around a round table. For each person, it is known whether they are infected at the beginning of the experiment. Zenik assumes that if a person is sick, in exactly one minute they infect the people sitting next to them at the table.

If Zenik’s assumption is correct, how much time will pass until all people at the table are infected?

Input

The first line contains an integer \(n\) — the number of people participating in the experiment.

In the second line, \(n\) numbers 0 or 1 are given. 1 means that the corresponding participant is infected at the beginning of the experiment, 0 — healthy.

Output

In a single line, print an integer — the minimum time after which all participants will become sick, if Zenik’s assumption is correct.

Constraints

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

at the beginning of the experiment, there is at least one infected participant.

Samples

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

Notes

After the first minute, only the third participant will be healthy, after the second — everyone is infected.