Evacuation Route

Disaster prevention research is active in Japan, and its importance has grown in recent years. Evaluating evacuation routes is one important research topic. This time we evaluate the safety of a straight corridor.

The corridor is divided into $W$ units, numbered $1, 2, 3, \ldots, W$ from one end to the other. Each unit in the corridor has exactly one of an entrance door, an exit door, or a fire door. There can be multiple entrance doors, exit doors, and fire doors in the corridor.

In this problem we assume a fire breaks out at time $t=0$. As a result, people outside the corridor who are trying to evacuate enter the corridor through entrance doors, and try to escape through exit doors to reach a safer place. Each evacuating person, in every unit of time, either moves to one unit or stays in the current unit. That is, if a person is in unit $i$ at time $t$, then at time $t+1$ that person can choose one of the three numbers $i-1, i, i+1$ that lies between $1$ and $W$ inclusive, and move to the unit with that number. A unit with a fire door becomes completely sealed after a certain time, so evacuating people cannot enter that unit. Also, people who were inside that unit can no longer move from it to another unit.

The goal of this problem is, given the information about each door, to compute the maximum number of people who can reach an exit door when the evacuating people act optimally.

The corridor information is given as $W$ integers $a_i$.

• $a_i = 0$ means unit $i$ is an exit door.
• $a_i < 0$ means unit $i$ becomes inaccessible from time $|a_i|$ onward because of a fire door.
• $a_i > 0$ means unit $i$ is an entrance door, and exactly one person appears in unit $i$ at each of times $t=0, 1, 2, \ldots, a_i-1$. A person who appears at time $t$ starts moving from time $t+1$ onward.

Multiple people may be in the same unit.

Find the maximum number of people who can reach an exit door.

The input is given in the following format.

$W$

$a_1$ $a_2$ $...$ $a_W$

Print the maximum number of people on one line.

• $1 ≤ W ≤ 10^5$
• $|a_i| ≤ 10^4$
• All input values are integers.