3467. Telefoni

单测试点时限: 1.0 秒

内存限制: 256 MB

There are desks in a room, placed from left to right, one next to each other. Some desks have phones on them, whereas some desks are empty. All phones are broken, so the phone on the ith desk will ring if the phone at jth desk rings, which is at most desks away from the th desk. In other words, it holds . The first and the last desk will always have a phone on them. In the beginning the leftmost phone rings. What is the minimal amount of new phones to be placed on the desks so that the last phone rings?

输入

The first line of input contains two positive integers, () and ().

The following line contains numbers or . If the th number is , then the ith desk from the left has a phone on it, otherwise the ith desk is empty.

输出

The first and only line of output must contain the required minimal number of phones.

样例

Input
5 2
1 0 0 0 1
Output
1
Input
4 1
1 0 1 1
Output
1
Input
8 2
1 1 0 0 1 0 0 1
Output
2

提示

In test cases worth points in total, it will hold .

33 人解决,35 已尝试。

40 份提交通过,共有 81 份提交。

7.9 EMB 奖励。

创建: 1 年前.

修改: 1 年前.

最后提交: 2 月,3 周前.

来源: COCI 2017

标签