Sugoroku

Interview

Time limit2sMemory limit512 MB

Summary

Squares 2 to N+1 are each marked 0 or 1; find the smallest die size j such that some sequence of rolls from 1 to j reaches or passes square N+2 without landing on any square marked 1.

Level: Medium5 of 10
Topics: Dynamic programming, BFS, Graph, Greedy
Solved: No attempts yet

Problem

JOI found a sugoroku board at his uncle's house. The board is a line of $N+2$ squares. Square 1 is the start and square $N+2$ is the goal. Every other square has either 0 or 1 written on it, and for each $i$ ( $1 \le i \le N$ ) the number written on square $i+1$ is $A_i$ .

The game begins with the piece on the start square. After that, you repeat one action: roll the die and move the piece forward by the number rolled. If the piece stops on a square with 1 written on it, the game is over. If the piece never stops on a square with 1 and it either stops exactly on the goal square or moves past the goal square, the game is cleared.

JOI went to a toy shop to buy a die for the game. The shop sells $N+1$ dice. Die $j$ ( $1 \le j \le N+1$ ) has $j$ faces, with $1, 2, \dots, j$ written one per face.

Among the dice for which some sequence of rolls clears the game, JOI buys the one with the fewest faces. Which die should he buy?

Input

The input is given from standard input in the following format.

N
A_1 A_2 ... A_N

Output

Print the number of faces of the die JOI should buy, on one line.

Constraints

$1 \le N \le 100$
$0 \le A_i \le 1$ ( $1 \le i \le N$ )

Examples3

Example 1
Input
```
5
0 1 0 0 0
```
Expected output
```
2
```
Example 2
Input
```
5
1 1 1 1 1
```
Expected output
```
6
```
Example 3
Input
```
7
0 0 1 0 1 1 0
```
Expected output
```
3
```