Cage Rabbit Propagation

On a rabbit farm, cages are arranged in a row and some cages initially contain rabbits (denoted by 1) while others are empty (denoted by 0). At the end of each breeding season, a rearrangement takes place following a very peculiar rule. A positive integer parameter K is chosen (which can be different in different moves). In that season, every cage that is currently occupied will send rabbits to the cage exactly K positions to its right, provided that the target cage exists (i.e. if the current cage is too close to the end then no rabbits are moved from it). The move is performed simultaneously for every occupied cage and the source cage remains occupied.

The goal is to make every cage occupied with rabbits using as few moves (seasons) as possible. Note that rabbits can only move to the right. Therefore, it is assumed that the 1^st cage is initially occupied; otherwise it would be impossible to ever occupy it.

Your task is to calculate the minimum number of moves required such that every cage becomes occupied.

Note on the move: In one move, you choose a positive integer K. Then for every cage i (1-indexed) that is occupied and for which i + K ≤ n (where n is the total number of cages), the cage i + K becomes occupied (if it wasn’t already). All moves occur simultaneously.

Hint: Focus on extending the contiguous prefix of occupied cages. In each move you must ensure that the very next cage (immediately after the current contiguous block starting at 1) gets occupied; then choose the move parameter that extends this contiguous block as far right as possible.

inputFormat

The input consists of two lines:

• The first line contains an integer n (1 ≤ n ≤ 1000) representing the number of cages.
• The second line contains n integers separated by spaces. Each integer is either 0 or 1; 1 indicates that the cage initially has rabbits and 0 indicates it is empty. It is guaranteed that the first cage (cage 1) is always occupied (i.e. its value is 1).

outputFormat

Output a single integer: the minimum number of moves required so that every cage becomes occupied.

sample

5
1 1 1 1 1

0