P7786 [COCI 2016/2017 #6] Telefoni

There are $N$ desks in an office arranged from left to right, and some desks have telephones. After the telephone on desk $j$ rings, the telephone on desk $i$ will also ring if and only if $|j-i|\le D$. You are given the current placement of telephones. Find the minimum number of telephones that need to be added so that the telephone on the last desk will ring. It is guaranteed that there is a telephone on the first desk and on the last desk.

The first line contains two positive integers $N$ and $D$, representing the number of desks and the maximum distance. The second line contains $N$ integers $A_i$. If $A_i=1$, it means there is a telephone on this desk; if $A_i=0$, it means there is no telephone.

One line with one integer, the minimum number of telephones that need to be added.

**Sample Explanation #1** Add a telephone on desk $2$, and then the telephone on desk $4$ can ring. **Sample Explanation #2** Add a telephone on desk $3$, and then the telephone on desk $5$ can ring. **Sample Explanation #3** Add one telephone each on desks $4$ and $7$, and then the telephone on desk $8$ can ring. **Constraints** For $50\%$ of the testdata, $1\le N\le 20$. For $100\%$ of the testdata, $1\le D\le N\le 3\times 10^5$. **Notes** The score of this problem follows the original COCI setting, with a full score of $80$. Translated from [COCI2016_2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #6](https://hsin.hr/coci/archive/2016_2017/contest6_tasks.pdf) _**T2 TELEFONI**_. Translated by ChatGPT 5