# Problem Statement

Joseph is just steps away from the fortress! All that's left is to cross one bridge and he will finally reach the entrance. Unfortunately, some parts of the bridge are at risk of collapsing because it is very old. Joseph's diving suit is very heavy and this object tires him out. He wants to avoid exhausting himself in order to arrive in good condition at the fortress.

The bridge is a passage of $N$ meters long, alternating between safe zones and fragile zones. The bridge is described using a table of $\emptyset$ and $1$: a number for every meter, $\emptyset$ indicates a position in a safe zone, and $1$ indicates a position in a fragile zone. A safe zone is represented by one or more consecutive $\emptyset$s, and a fragile zone by one or more consecutive $1$s.

During his crossing, at each meter, Joseph Swims can either move by walking or swimming. Joseph Swims must swim through all fragile zones to avoid causing the bridge to collapse. In safe zones, he can either swim or walk.

## Exercise Constraint "Just Passing Through," Joseph is not required to walk in every safe zone. This time, he can swim through an entire safe zone. On the other hand, Joseph must walk at least once during his journey.

However, Joseph has a certain endurance $E \geq 0$ that allows him to swim for a maximum of $E$ meters before he must switch to walking. After swimming, he must walk for a minimum of $R$ meters before starting his next swim or reaching the end of the bridge. (Joseph cannot start a walking phase during the last $R-1$ meters. Additionally, if Joseph starts with a walking phase, he must walk for at least $R$ meters before starting to swim.)

Joseph's strength is called the value of $R-E$. Help Joseph Swims find a strategy for movement that maximizes his strength.

# Input

The input will contain:

- On the first line, an integer: $N$, the length (in meters) of the bridge.
- On the next line, a list of $N$ integers separated by spaces: $\text{bridge}$, the table representing the safe zones and fragile zones of the bridge. One number per meter: A $\emptyset$ corresponds to a position in a safe zone, and a $1$ corresponds to a position in a fragile zone.

# Output

Print the maximum strength value that Joseph Swims can achieve by crossing the bridge.

# Constraints

- $1 \leq N \leq 1000$
- $\text{bridge}_i \in \{0,1\}$
- There is always at least one rest zone

# Performance Constraints

- $1 \leq N \leq 500000$

# Execution Constraints

- Maximum memory usage: 100,000 kilobytes
- Maximum execution time: 500 milliseconds

# Input/Output Examples

## Input Example

```
9
1 0 1 0 0 0 1 1 1
```

## Output Example

```
0
```

# Comment

Joseph Swims is faced with a bridge 9 meters long. To maximize his strength, Joseph can consider an endurance value of $E = 3$ and a rest value of $R = 3$.

![Bridge Illustration](https://example.com/illustration.png)

His journey would look like this: - First, he swims over the first two fragile zones for three meters ($3 \leq E$); - He then covers the next three meters, in the second safe zone, by walking ($3 \geq R$); - Finally, he swims the last three meters to cross the last fragile zone ($3 \leq E$).

This example journey gives Joseph a strength of $R - E = 3 - 3 = 0$. It is not possible to cross the bridge with a greater strength.

## Input Example

```
10
1 1 0 0 0 0 1 0 0 0
```

## Output Example

```
1
```

# Comment

Joseph can maximize his energy score with $E = 2$ and $R = 3$. The score is then $R - E = 1$. Note that Joseph cannot take a rest value of $R = 4$, as he would not have enough time to complete the last rest phase.

# Submit Your Solution