Thumbtacks

Interview

Time limit1sMemory limit128 MB

Summary

Find the smallest jump that crosses the bridge using only planks without thumbtacks.

Level: Easy2 of 10
Topics: Array
Solved: No attempts yet

Problem

Jas is on his way home and must cross a bridge, but someone has laid a straight line of thumbtacks across it. The bridge is so narrow that there is no way to step around them, so the thumbtacks have to be jumped over. They are not all packed together: here and there are spots where Jas can put his foot down.

The bridge is made of $n$ planks, and each plank may hold a thumbtack. Jas can stand on a plank without a thumbtack, but not on one that has a thumbtack. We want to know how strong a jump Jas needs in order to reach the other side of the bridge. The jump length is the maximum number of planks Jas can clear in a single jump.

Input

The first line contains one integer $n$ ( $1 \le n \le 10^6$ ), the number of planks that make up the bridge. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ , each equal to $0$ or $1$ , where $a_i$ describes the $i$ -th plank: $0$ if the plank has no thumbtack, $1$ if it does.

Output

Print a single integer: the jump length Jas must have in order to get to the other side of the bridge.

Examples1

Example 1
Input
```
7
0 1 0 1 1 1 1
```
Expected output
```
4
```