409629: GYM103648 F Firebird

F. Firebirdtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The phoenix is an immortal bird from the folklore of various cultures. In particular, it has the interesting property that when it dies, it bursts into flames and then is reborn from the ashes.

Barblewindow has just acquired himself a baby phoenix, and wishes to track its development. Every day, he records the age of his phoenix in days. Whenever the phoenix dies and is reborn, he restarts the count (i.e. the phoenix is 0 days old on the day it dies and is reborn).

Unfortunately, during one of the phoenix's rebirths, Barblewindow's notes caught fire, so some of his records are missing. Barblewindow knows that a phoenix can only die after it is at least $$$K$$$ days old. Given the remaining records, can you help him determine the maximum number of times his phoenix could have been reborn?

Input

The first line contains two integers $$$N, K$$$, where $$$N$$$ total days have passed since Barblewindow first acquired his phoenix, and a phoenix can only die after it is at least $$$K$$$ days old. $$$(2 \le N \le 10^6, 2 \le K \le N)$$$

The next line contains $$$N$$$ space-separated integers $$$a_1,a_2,...,a_N$$$ $$$(-1 \le a_i \le N)$$$ where:

• $$$a_i = -1$$$ if the $$$i$$$th day's records are missing, or
• the phoenix was $$$a_i$$$ days old on day $$$i$$$ otherwise.

The first integer $$$a_1$$$ will always be 0. It is guaranteed that records are consistent (there will always be a way to fill in the missing records in a way that satisfies the constraints).Output

Output a single integer denoting the maximum number of times Barblewindow's phoenix could have been reborn. We consider the phoenix's initial birth (day 0) to be a rebirth.

ExampleInput

10 3
0 -1 -1 3 -1 -1 -1 -1 -1 1

Output

3

Note

In the first example, one way to fill in the missing records is as follows: $$$[0, 1, 2, 3, 4, 0, 1, 2, 0, 1]$$$, which corresponds to 3 rebirths including the initial birth.