Farmer Ron in Colorado costruisce un centro sciistico per mucche, ma il budget consente un solo impianto. La monorotaia collega supporto iniziale di cemento a quello finale tramite intermedi, ciascuno alto0 sopra il terreno. Acciaio rettilineo collega ogni coppia adiacente e deve stare ovunque sopra il suolo.

Parsimonioso, FR minimizza supporti. Misurò $N$ terreni uguali $(2 \le N \le 5,000)$ di altezza intera $H$ $(0 \le H \le 1,000,000,000)$. Sicurezza impone distanza adiacente al massimo $K$ unità $(1 \le K \le N - 1)$. Acciaio rigido forma retta.

Trova minimi supporti: acciaio interamente sopra o tangente al terreno, distanza orizzontale adiacente al massimo $K$, supporti su primo e ultimo terreno.

Input

• Riga $1$: due interi separati da spazio $N$, $K$.
• Righe $2..N+1$: riga $i+1$ contiene altezza intera del terreno $i$.

Output

• Riga $1$: intero, minimo di torri sotto tali vincoli.

Esempi

Input 1

13 4
0
1
0
2
4
6
8
6
8
8
9
11
12

Output 1

5

Nota

5 supporti in1, 5, 7, 9, 13. Acciaio tangente in4 punti:1–5, 5–7, 7–9, 12–13.

4 supporti in1, 5, 9, 13 danno acciaio sotterraneo5–9. In1, 7, 13 resta sopra ma7 e13 distano oltre4 orizzontalmente. Meno di5 supporti con distanze adiacenti al massimo4 è impossibile.

Fonte originale: https://github.com/ivankra/acm/blob/master/usaco/MAR06/prob/gold-en.htm

Autore del problema: Adam Rosenfield, 2004